Codeforces Deltix Round, Spring 2021 F問題 - Favorite Game

Source

Codeforces Deltix Round, Spring 2021 F問題 (3000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20210607-1）のコード

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

//no-unlocked
int N, M, TX[20], TY[], QX[100], QY[], QT[];
int mxs[101][17000];
int mincost1[20][17000];
int mincost2[100][17000];
{
  int i, j, k, res = 0, nx, ct, dmask, score, mask;
  dimcomp2 dm(101,17000);
  DijkstraHeap<int> hp;
  hp.walloc(101*17000,1);

  rd(N,M,(TX,TY)(N),(QX,QY,QT)(M));
  sortA(M,QT,QX,QY);

  rep(i,N) rep(mask,1<<N){
    mincost1[i][mask] = int_inf;
    rep(k,N) if(BIT_ith(mask,k)) mincost1[i][mask] <?= abs(TX[k]-TX[i]) + abs(TY[k]-TY[i]);
  }
  rep(i,M) rep(mask,1<<N){
    mincost2[i][mask] = int_inf;
    rep(k,N) if(BIT_ith(mask,k)) mincost2[i][mask] <?= abs(TX[k]-QX[i]) + abs(TY[k]-QY[i]);
  }

  rep(i,M) rep(j,1<<N) mxs[i][j] = -1;
  rep(i,M) mxs[i][0] = 1;
  rep(i,N) hp.change(dm(0,1<<i), 0);

  k = 0;
  while(k < M){
    nx = if[hp.size, hp.val[hp.hp[0]], int_inf];
    if(QT[k] <= nx){
      rep(mask,1<<N) if(mxs[k][mask] >= 0){
        res >?= mxs[k][mask];
        score = mxs[k][mask];
        ct = QT[k];

        if(mask){
          rep(j,N) if(!BIT_ith(mask,j)) hp.change(dm(score, mask|(1<<j)), ct + mincost1[j][mask]);
          rep(j,M) if(ct + mincost2[j][mask] <= QT[j]) mxs[j][mask] >?= score + 1;
        }

        rep(j,N) if(!BIT_ith(mask,j)) hp.change(dm(score, mask|(1<<j)), ct + abs(TX[j]-QX[k]) + abs(TY[j]-QY[k]));
        rep(j,k+1,M){
          if(ct + abs(QX[j]-QX[k]) + abs(QY[j]-QY[k]) > QT[j]) continue;
          mxs[j][mask] >?= score + 1;
        }
      }
      k++;
    } else {
      dmask = hp.pop();
      dm(dmask, score, mask);
      ct = hp.val[dmask];
      rep(j,N) if(!BIT_ith(mask,j)) hp.change(dm(score, mask|(1<<j)), ct + mincost1[j][mask]);
      rep(j,k,M) if(ct + mincost2[j][mask] <= QT[j]) mxs[j][mask] >?= score + 1;
    }
  }

  wt(res);
}

Current time: 2024年04月17日04時23分41秒
Last modified: 2021年06月07日19時36分40秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces
トップページに戻る

Logged in as: unknown user (not login)