#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ti3 tuple<int, int, int>
#define ti4 tuple<int, int, int, int>
// This is like my secret account; yes it's like that ~ Baek Jiheon, Feel Good (Secret Code)
using namespace std;
int psum[20001];
int result[51][20001];
int n;
struct node{
int s, e, m, val, lazyadd;
node *left;
node *right;
node(int _s, int _e): s(_s), e(_e), m((_s+_e)/2), val(0), lazyadd(0){
if (_s != _e){
left = new node(_s, m);
right = new node(m + 1, _e);
}
}
int value(){
if (s == e){val += lazyadd; lazyadd=0; return val;}
val += lazyadd;
right->lazyadd += lazyadd;
left->lazyadd += lazyadd;
lazyadd = 0;
return val;
}
void add(int x, int y, int up){
if (s == x && e == y) lazyadd += up;
else {
if (x > m) right->add(x, y, up);
else if (y <= m) left->add(x, y, up);
else {left->add(x, m, up); right->add(m+1, y, up);}
val = min(left->value(), right->value());
}
}
int rmq(int _s, int _e){
value();
if (s==_s && e== _e) return val;
if (_s > m) return right->rmq(_s, _e);
else if (_e <= m) return left->rmq(_s, _e);
return min(left->rmq(_s, m), right->rmq(m+1, _e));
}
} *root;
int dp[20001][51];
int prev1[51];
main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int t, s; cin >> n >> t >> s;
for (int i = 1; i <= t; i++){
cin >> psum[i];
psum[i] += psum[i-1];
}
for (int i = 0; i < n; i++){
for (int j = 1; j <= t; j++){
char x; cin >> x;
int g = x - '0';
result[i][j] = g;
}
}
dp[0][0] = 0;
for (int i = 1; i <= t; i++){
dp[i][0] = 1e15;
}
for (int i = 1; i <= s; i++){
dp[0][i] = 1e15;
for (int j = 0; j < n; j++){
prev1[j] = -1;
}
root = new node(0, t);
for (int j = 1; j <= t; j++){
dp[j][i] = 1e15;
// add result j.
for (int k = 0; k < n; k++){
if (result[k][j] == 0){
if (prev1[k] != -1){
for (int d = prev1[k]-1; d < j-1; d++){
root->add(d, d, -(psum[j-1] - psum[d]));
}
prev1[k] = -1;
}
} else {
if (prev1[k] == -1){
root->add(j-1, j-1, psum[j] - psum[j-1]);
prev1[k] = j;
} else {
root->add(prev1[k]-1, j-1, psum[j] - psum[j-1]);
}
}
}
root->add(j-1, j-1, dp[j-1][i-1]);
dp[j][i] = min(dp[j][i], root->rmq(0, j-1));
/*
for (int k = 0; k < j; k++){
dp[j][i] = min(dp[j][i], dp[k][i-1] + cost(k+1, j));
}
*/
}
cout << dp[t][i] << '\n';
}
}
Compilation message
popeala.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
48 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
5 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
514 ms |
3968 KB |
Output is correct |
| 2 |
Correct |
477 ms |
4012 KB |
Output is correct |
| 3 |
Correct |
527 ms |
4064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2060 ms |
13588 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
5 ms |
596 KB |
Output is correct |
| 3 |
Correct |
514 ms |
3968 KB |
Output is correct |
| 4 |
Correct |
477 ms |
4012 KB |
Output is correct |
| 5 |
Correct |
527 ms |
4064 KB |
Output is correct |
| 6 |
Execution timed out |
2060 ms |
13588 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
