AtCoder Beginner Contest 136 E問題 - Max GCD

Source

AtCoder Beginner Contest 136
問題文

問題概要

省略

解法

省略

cLay（version 20190822-2）のコード

C++に変換後のコードはこちら

int N, K, A[500];

int b[500];
int s;
int ys, y[10000];
{
  int i, j, k, m, res;
  ll nd, cur;

  rd(N,K,A(N));
  s = sum(A(N));
  ys = Divisor(s, y);

  rep(m,ys){
    rep(i,N) b[i] = A[i] % y[m];
    sort(b, b+N);
    nd = cur = 0;
    j = 0;
    for(i=N-1;i>=0;i--){
      if(b[i]==0) break;
      nd += y[m] - b[i];
      cur += y[m] - b[i];
      b[i] = 0;
      while(cur > 0 && j<i){
        k = min(cur, b[j]);
        b[j] -= k;
        cur -= k;
        if(b[j]==0) j++;
      }
    }
    if(nd <= K) res = y[m];
  }

  wt(res);
}

Current time: 2024年04月20日07時45分15秒
Last modified: 2019年08月22日23時21分23秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC136 ABC_E
トップページに戻る

Logged in as: unknown user (not login)