2019年09月26日01時48分16秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
Codeforces Round #587 DIV3 F問題
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, K;
char S[200002];
ll dp[200002];
{
int i, j;
ll tmp;
segtree_Point_Minval<ll> t;
rd(N,K,S);
rep(i,N) S[i] -= '0';
rep(i,N) dp[i+1] = ll_inf;
t.malloc(N+1);
t.setN(N+1);
rep(i,N+1) t[i] = dp[i];
t.build();
rep(i,N){
if(dp[i+1] > dp[i] + i + 1){
dp[i+1] = dp[i] + i + 1;
t.change(i+1, dp[i+1]);
}
if(S[i]){
tmp = t.getMinVal(max(0,i-K), N) + i + 1;
j = min(N, i+1+K);
if(dp[j] > tmp){
dp[j] = tmp;
t.change(j, tmp);
}
}
}
wt(dp[N]);
}
Current time: 2024年05月06日11時23分12秒
Last modified: 2019年09月26日01時48分16秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF587 CF_Div3_F
トップページに戻る
Logged in as: unknown user (not login)