# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
127823 | sealnot123 | Popeala (CEOI16_popeala) | C++14 | 157 ms | 13932 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define push_back pb
#define emplace_back eb
using namespace std;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
const int N = 20005, M = 52;
LL qs[N], MI[M][M], dp[N][M];
int P[M], PP[N], PPP[M], last[N][M];
char str[N];
int main(){
int n, m, s;
int i,j,k,l,a,b,c,d;
scanf("%d%d%d",&m,&n,&s);
for(i=1;i<=n;i++) dp[i][0] = 1e16;
for(i=1;i<=s;i++) dp[0][i] = 1e16;
for(i=1;i<=s;i++){
for(j=0;j<=m;j++) MI[i][j] = 1e16;
}
for(i=1;i<=n;i++) scanf("%lld",&qs[i]), qs[i]+=qs[i-1];
for(i=1;i<=m;i++){
scanf(" %s",str+1);
for(j=1;j<=n;j++){
if(str[j] == '0') last[j][i] = j;
else last[j][i] = last[j-1][i];
/*printf("%d ",last[j][i]);*/
}
/*printf("\n");*/
P[i] = 1;
}
for(i=0;i<=m;i++) PPP[i] = 1;
for(i=1;i<=n;i++){
PP[i] += m;
for(j=1;j<=m;j++){
while(P[j] <= last[i][j]) PP[P[j]++]--;
}
/*for(j=0;j<=n;j++) printf("%d ",PP[j]);
printf("\n");*/
for(j=0;j<=m;j++){
while(PPP[j] <= i && PP[PPP[j]] <= j){
a = PPP[j];
for(k=1;k<=s;k++) MI[k][j] = min(MI[k][j], dp[a-1][k-1] - qs[a-1]*j);
PPP[j]++;
}
}
for(j=1;j<=s;j++){
dp[i][j] = 1e16;
for(k=0;k<=m;k++) dp[i][j] = min(dp[i][j], qs[i]*k + MI[j][k]);
}
}
for(i=1;i<=s;i++) printf("%lld\n",dp[n][i]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |