#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ifstream in ("popeala.in");
long t, n, s;
in >> n >> t >> s;
long long cumu[t+1];
cumu[0] = 0;
for(long i = 1; i<=t; i++){
in >> cumu[i];
cumu[i]+=cumu[i-1];
}
bool got[n][t];
for(long i = 0; i<n; i++){
string str;
in >> str;
for(long j = 0; j<t; j++){
got[i][j] = str[j]=='1';
}
}
vector<vector<long long> > best;
best.resize(s+1);
for(long a = 0; a<=s; a++){
for(long b = 0; b<=t; b++){
best[a].push_back(2000000002L);
}
}
best[0][0] = 0L;
for(long i = 0; i<s; i++){
long long last[n];
for(long j= 0; j<n; j++){
last[j] = -1L;
}
long long inactive[t+1];
long long mini[n+1];
for(long j = 0; j<=n; j++){
mini[j] = 2000000002L;
}
for(long j = 0; j<t; j++){
mini[0] = min(mini[0],best[i][j]);
inactive[j] = 0;
for(long k = 0; k<=n; k++){
mini[k] += (long long)(n-k)*(cumu[j+1]-cumu[j]);
}
for(long k = 0; k<n; k++){
if(got[k][j]){
continue;
}
for(long l = j; l>=0; l--){
if(l>last[k]){
inactive[l]++;
mini[inactive[l]] = min(mini[inactive[l]],best[i][l]+(cumu[j+1]-cumu[l])*(long long)(n-inactive[l]));
}
else{
break;
}
}
last[k] = j;
}
for(long k = 0; k<=n; k++){
best[i+1][j+1] = min(best[i+1][j+1],mini[k]);
}
}
}
for(long i = 1; i<=s; i++){
cout << best[i][t] << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
