| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1032828 |
2024-07-24T09:28:55 Z |
김은성(#10965) |
Popeala (CEOI16_popeala) |
C++17 |
|
50 ms |
11344 KB |
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
int p[20009], dp[52][20009];
int n, r[52][20009], re[52][20009];
char res[20009];
int tree[52][1<<16];
int ctree[1<<16], idx[52], lazy[1<<16];
int solved(int s, int e){
int ans = 0, i;
for(i=1; i<=n; i++){
if(re[i][e] - re[i][s-1] == e-s+1)
ans++;
}
return ans;
}
void settree(int idx, int i, int v, int l, int r){ //-idx * p[k] + dp[i][k] �� ����
if(l==r)
tree[idx][v] = -idx * p[l] + dp[i][l];
else{
int mid = (l+r)/2;
settree(idx, i, 2*v,l , mid);
settree(idx, i, 2*v+1, mid+1, r);
tree[idx][v] = min(tree[idx][2*v], tree[idx][2*v+1]);
}
}
int minquery(int idx, int v, int l, int r, int s, int e){
if(e<l || r<s)
return INF;
if(s<=l && r<=e)
return tree[idx][v];
int mid = (l+r)/2;
return min(minquery(idx, 2*v,l , mid, s, e), minquery(idx, 2*v+1, mid+1, r, s, e));
}
void update(int v, int l, int r, int s, int e){
if(lazy[v]){
ctree[v] += lazy[v];
if(l!=r){
lazy[2*v] += lazy[v];
lazy[2*v+1] += lazy[v];
}
lazy[v] = 0;
}
if(e<l || r<s)
return;
if(s<=l && r<=e){
ctree[v]++;
if(l!=r){
lazy[2*v]++;
lazy[2*v+1]++;
}
}
else{
int mid = (l+r)/2;
update(2*v,l , mid, s, e);
update(2*v+1, mid+1, r, s, e);
ctree[v] = max(ctree[2*v], ctree[2*v+1]);
}
}
int bound(int v, int l, int r, int x){ //�����ڼ� >= x �� �ִ��� k
if(lazy[v]){
ctree[v] += lazy[v];
if(l!=r){
lazy[2*v] += lazy[v];
lazy[2*v+1] += lazy[v];
}
lazy[v] = 0;
}
// printf("x=%d\n", x);
//printf("ctree=%d lazy=%d x=%d\n", ctree[v], lazy[v], x);
if(ctree[v] + lazy[v] < x)
return -1;
if(l==r)
return l;
int mid = (l+r)/2;
if(ctree[2*v+1] + lazy[2*v+1] >= x)
return bound(2*v+1, mid+1, r, x);
return bound(2*v, l, mid, x);
}
int main(){
int t, s, i, j, k;
scanf("%d %d %d", &n, &t, &s);
for(i=1; i<=t; i++){
scanf("%d", &p[i]);
p[i] += p[i-1];
}
for(i=1; i<=n; i++){
scanf(" %s", res+1);
for(j=1; j<=t; j++){
r[i][j] = res[j] - '0';
re[i][j]= re[i][j-1] + r[i][j];
}
}
dp[1][0] = INF;
for(i=1; i<=t; i++)
dp[1][i] = solved(1, i) * p[i];
for(i=2; i<=s; i++){
for(j=0; j<=n; j++){
settree(j, i-1, 1, 1, t);
}
for(j=1; j<=n; j++)
idx[j] = 1;
memset(ctree, 0, sizeof(ctree));
memset(lazy, 0, sizeof(lazy));
for(j=1; j<=t; j++){
dp[i][j] = INF;
for(k=1; k<=n; k++){
if(!r[k][j]){
update(1, 1, t, idx[k], j);
//printf("idx[k]=%d j=%d\n", idx[k], j);
idx[k]=j+1;
}
}
for(k=0; k<=n; k++){
int lo = bound(1, 1, t, n-k);
// printf("k=%d lo=%d\n", n-k, lo);
if(lo==-1)
continue;
dp[i][j] = min(dp[i][j], p[j] * k + minquery(k, 1, 1, t, 1, min(lo-1, j-1)));
}
if(i>j)
assert(dp[i][j] == INF);
//printf("dp[%d][%d]=%d\n", i, j, dp[i][j]);
}
}
for(i=1;i <=s; i++)
printf("%d\n", dp[i][t]);
return 0;
}
Compilation message
popeala.cpp: In function 'int main()':
popeala.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
82 | scanf("%d %d %d", &n, &t, &s);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d", &p[i]);
| ~~~~~^~~~~~~~~~~~~
popeala.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf(" %s", res+1);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
2652 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
3672 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
11344 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2908 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
2652 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
