Codeforces Deltix Round, Spring 2021 F問題 (3000pt)
Problem description
省略
省略
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月19日11時30分29秒
Last modified: 2021年06月07日19時36分40秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces
トップページに戻る
Logged in as: unknown user (not login)