| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1032830 |
2024-07-24T09:29:35 Z |
김은성(#10965) |
Popeala (CEOI16_popeala) |
C++17 |
|
2000 ms |
26744 KB |
#include <bits/stdc++.h>
using namespace std;
const long long INF = 2147000000;
long long p[20009], dp[52][20009];
long long n, r[52][20009], re[52][20009];
char res[20009];
long long tree[52][1<<16];
long long ctree[1<<16], idx[52], lazy[1<<16];
long long solved(long long s, long long e){
long long 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(long long idx, long long i, long long v, long long l, long long r){ //-idx * p[k] + dp[i][k] �� ����
if(l==r)
tree[idx][v] = -idx * p[l] + dp[i][l];
else{
long long 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]);
}
}
long long minquery(long long idx, long long v, long long l, long long r, long long s, long long e){
if(e<l || r<s)
return INF;
if(s<=l && r<=e)
return tree[idx][v];
long long 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(long long v, long long l, long long r, long long s, long long 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{
long long 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]);
}
}
long long bound(long long v, long long l, long long r, long long 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;
}
// prlong longf("x=%d\n", x);
//prlong longf("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;
long long 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(){
long long 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);
//prlong longf("idx[k]=%d j=%d\n", idx[k], j);
idx[k]=j+1;
}
}
for(k=0; k<=n; k++){
long long lo = bound(1, 1, t, n-k);
// prlong longf("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)));
}
//prlong longf("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:13: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
82 | scanf("%d %d %d", &n, &t, &s);
| ~^ ~~
| | |
| int* long long int*
| %lld
popeala.cpp:82:16: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
82 | scanf("%d %d %d", &n, &t, &s);
| ~^ ~~
| | |
| int* long long int*
| %lld
popeala.cpp:82:19: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
82 | scanf("%d %d %d", &n, &t, &s);
| ~^ ~~
| | |
| int* long long int*
| %lld
popeala.cpp:84:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
84 | scanf("%d", &p[i]);
| ~^ ~~~~~
| | |
| | long long int*
| int*
| %lld
popeala.cpp:125:18: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
125 | printf("%d\n", dp[i][t]);
| ~^ ~~~~~~~~
| | |
| int long long int
| %lld
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 |
3416 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
3164 KB |
Output is correct |
| 2 |
Correct |
89 ms |
5200 KB |
Output is correct |
| 3 |
Correct |
96 ms |
3156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
519 ms |
8128 KB |
Output is correct |
| 2 |
Correct |
828 ms |
9296 KB |
Output is correct |
| 3 |
Correct |
1006 ms |
10324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
2 ms |
1884 KB |
Output is correct |
| 3 |
Correct |
97 ms |
3164 KB |
Output is correct |
| 4 |
Correct |
89 ms |
5200 KB |
Output is correct |
| 5 |
Correct |
96 ms |
3156 KB |
Output is correct |
| 6 |
Correct |
519 ms |
8128 KB |
Output is correct |
| 7 |
Correct |
828 ms |
9296 KB |
Output is correct |
| 8 |
Correct |
1006 ms |
10324 KB |
Output is correct |
| 9 |
Correct |
1609 ms |
18164 KB |
Output is correct |
| 10 |
Execution timed out |
2009 ms |
26744 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
