#include <bits/stdc++.h>
using namespace std;
const int INF = 2.1e9;
int testsums[20001];
int people;
int numTests;
int numTasks;
struct ragetree {
int ragetreemax[4*20001];
int ragetreelazy[4*20001];
void pushdown(int idx) {
if(ragetreelazy[idx] != INF) {
ragetreelazy[2*idx] = min(ragetreelazy[2*idx], ragetreelazy[idx]);
ragetreelazy[2*idx+1] = min(ragetreelazy[2*idx+1], ragetreelazy[idx]);
ragetreelazy[idx] = INF;
}
}
void pullup(int idx) {
assert(ragetreelazy[idx] == INF);
ragetreemax[idx] = max(ragetreemax[2*idx], ragetreemax[2*idx+1]);
if(ragetreelazy[2*idx] != INF) ragetreemax[idx] = max(ragetreemax[idx], ragetreelazy[2*idx]);
if(ragetreelazy[2*idx+1] != INF) ragetreemax[idx] = max(ragetreemax[idx], ragetreelazy[2*idx+1]);
}
ragetree() {
for(int i = 0; i < 4*20001; i++) {
ragetreemax[i] = INF;
}
for(int i = 0; i < 4*20001; i++) {
ragetreelazy[i] = INF;
}
}
void update(int idx, int l, int r, int lhs, int rhs, int v) {
if(v >= ragetreelazy[idx]) return;
if(v >= ragetreemax[idx]) return;
if(l >= lhs && r <= rhs) {
ragetreelazy[idx] = v;
return;
}
pushdown(idx);
int m = (l+r)/2;
if(m >= lhs) update(2*idx, l, m, lhs, rhs, v);
if(m+1 <= rhs) update(2*idx+1, m+1, r, lhs, rhs, v);
pullup(idx);
}
void update(int l, int r, int v) {
assert(v <= 2000000000);
update(1, 0, 20000, l, r, v);
}
int query(int idx, int l, int r, int i) {
if(l==r) return min(ragetreemax[idx], ragetreelazy[idx]);
pushdown(idx);
int ret;
int m = (l+r)/2;
if(i <= m) ret = query(2*idx, l, m, i);
else ret = query(2*idx+1, m+1, r, i);
pullup(idx);
return ret;
}
int query(int i) {
return query(1, 0, 20000, i);
}
};
string l[50];
int firstWrong[50][20001];
ragetree dp[51];
int bad[50];
void compute() {
for(int i = 0; i < numTests; i++) {
for(int j = 0; j < people; j++) {
bad[j] = firstWrong[j][i];
}
sort(bad, bad+people);
{
int good = people;
for(int a = 0; a < people; a++) {
if(bad[a] == i) {
good--;
}
else break;
}
for(int a = 0; a < numTasks; a++) {
int curr = dp[a].query(i);
if(curr == INF) continue;
dp[a+1].update(i+1, i+1, curr + good * (testsums[i+1] - testsums[i]));
}
}
int numGood = people;
int lhs = i+1;
for(int j = 0; j < people;) {
int k = j+1;
while(k < people && bad[j] == bad[k]) {
k++;
}
if(numGood < people) {
for(int a = 0; a < numTasks; a++) {
int curr = dp[a].query(i);
if(curr == INF) continue;
dp[a+1].update(lhs, bad[j], curr + numGood * (testsums[bad[j]] - testsums[i]));
}
}
lhs = bad[j]+1;
numGood -= k-j;
j = k;
}
if(lhs <= numTests) {
for(int a = 0; a < numTasks; a++) {
int curr = dp[a].query(i);
if(curr == INF) continue;
dp[a+1].update(lhs, numTests, curr);
}
}
}
}
void solve() {
cin >> people >> numTests >> numTasks;
for(int i = 1; i <= numTests; i++) {
cin >> testsums[i];
testsums[i] += testsums[i-1];
}
dp[0].update(0, 0, 0);
for(int i = 0; i < people; i++) {
cin >> l[i];
firstWrong[i][numTests] = numTests;
for(int j = numTests-1; j >= 0; j--) {
if(l[i][j] == '0') {
firstWrong[i][j] = j;
}
else {
firstWrong[i][j] = firstWrong[i][j+1];
}
}
}
compute();
for(int i = 1; i <= numTasks; i++) {
cout << dp[i].query(numTests);
cout << "\n";
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
32376 KB |
Output is correct |
| 2 |
Incorrect |
35 ms |
32544 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
206 ms |
32684 KB |
Output is correct |
| 2 |
Correct |
201 ms |
32900 KB |
Output is correct |
| 3 |
Correct |
208 ms |
32900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
836 ms |
33284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
32376 KB |
Output is correct |
| 2 |
Incorrect |
35 ms |
32544 KB |
Output isn't correct |
