AtCoder Beginner Contest 147 F問題 - Sum Difference

Source

AtCoder Beginner Contest 147
問題文

問題概要

省略

解法

省略

cLayversion 20200119-1)のコード

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

ll N, X, D;

int sz;
ll mns[2d5], mxs[2d5];

{
  ll i, j, g, mn, mx, all;
  ll res = 0;

  rd(N,X,D);

  if(X==D==0) wt(1), return 0;
  if(D==0) wt(N+1), return 0;

  if(D < 0) D = -D, X = -X;
  g = gcd(abs(X),D);
  X /= g;
  D /= g;

  all = N * (N-1) / 2 * D;
  REP(i,min(D,N+1)){
    sz = 0;
    rep(j,i,N+1,D){
      mx = X * (N-j) + (all - j * (j-1) / 2 * D);
      mn = X * (N-j) + ((N-j) * (N-j-1) / 2 * D);
      arrInsert(sz,sz,mns,mn,mxs,mx);
    }

    sortA(sz, mns, mxs);
    mx = -ll_inf;
    rep(j,sz){
      mns[j] >?= mx + D;
      mx >?= mxs[j];
      if(mxs[j] >= mns[j]) res += (mxs[j] - mns[j]) / D + 1;
    }
  }

  wt(res);
}

Current time: 2024年03月29日02時51分10秒
Last modified: 2020年01月19日05時11分33秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC147 ABC_F
トップページに戻る

Logged in as: unknown user (not login)

ログイン: