Codeforces Round #597 DIV2 D問題 - Shichikuji and Power Grid

Source

Codeforces Round #597 DIV2 D問題 (1750pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20191027-1)のコード

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

//no-unlocked
int N, X[2000], Y[2000], C[2000], K[2000];
int vis[2000], bk[2000]; ll mn[2000];

ll res;
int ps, p[2000], ms, ma[2000], mb[2000];
{
  int i, j, k;
  ll cost;
  rd(N, (X,Y)(N), C(N), K(N));

  rep(i,N) mn[i] = C[i], bk[i] = N;
  for(;;){
    i = argmin(mn(N));
    if(vis[i]++) break;
    res += mn[i];
    mn[i] = ll_inf;
    if(bk[i]==N) p[ps++] = i;
    else         arrInsert(ms,ms,ma,i,mb,bk[i]);
    rep(k,N) if(vis[k]==0){
      cost = (ll) (K[i] + K[k]) * (abs(X[i]-X[k]) + abs(Y[i]-Y[k]));
      if(mn[k] > cost) mn[k] = cost, bk[k] = i;
    }
  }

  wt(res);
  wt(ps);
  wt(p(ps)+1);
  wt(ms);
  rep(i,ms) wt(ma[i]+1, mb[i]+1);

}

Current time: 2021年09月17日15時30分51秒
Last modified: 2019年11月02日02時57分06秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF597 CF_Div2_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン: