#include <bits/stdc++.h>
using namespace std;
#define min(a, b) (a < b ? a : b)
#define ll long long
int n, t, s;
int pts[20005];
ll pre[20005];
int nxt[55][20005];
int can[55][20005];
ll dp[20005][55];
// struct Point {
// int x, c;
// int eval (int m) {
// return m * x + c;
// }
// };
// int rek(int cur, int gr) {
// if (cur >= t) {
// if (gr != 0) return 1e12;
// // if (gr == s) return 1e12;
// return 0;
// }
// if (gr == 0) return 1e12;
// ll& res = dp[cur][gr];
// if (res != -1) return res;
// res = 1e12;
// res = min(1ll * res, 1ll * rek(cur + 1, gr - 1) + 1ll * pts[cur] * n);
// vector<int> block;
// for (int i = 0; i < n; ++i) {
// block.push_back(nxt[i][cur]);
// }
// sort(block.begin(), block.end());
// // cout << "LST FOR " << cur << endl;
// // for (auto i : block) cout << i << ' ';
// // cout << endl;
// // for (int i = cur; i < t; ++i) {
// // block.push_back(i);
// // }
// int act = n;
// vector<int> vis(n);
// for (auto i : block) {
// if (i == t) break;
// for (int j = 0; j < n; ++j) {
// if (vis[j]) continue;
// if (nxt[j][i] <= i) {
// vis[j] = 1;
// --act;
// }
// }
// // --act;
// res = min(1ll * res, 1ll * rek(i + 1, gr - 1) + 1ll * (pre[i] - (cur ? (pre[cur - 1]) : 0)) * act);
// // cout << "CUR " << cur << endl;
// // cout << i << ' ' << act << ' ' << 1ll * rek(i + 1, gr - 1) + 1ll * (pre[i] - (cur ? (pre[cur - 1]) : 0)) * act << endl;
// }
// // cout << endl;
// res = min(1ll * res, 1ll * rek(t, gr - 1) + 1ll * (pre[t - 1] - (cur ? pre[cur - 1] : 0)) * act);
// // cout << act << endl;
// return res;
// }
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// memset(dp, -1, sizeof dp);
cin >> n >> t >> s;
for (int i = 0; i < t; ++i) cin >> pts[i];
pre[0] = pts[0];
for (int i = 1; i < t; ++i) pre[i] = pre[i - 1] + pts[i];
for (int i = 0; i < n; ++i) {
string s;
cin >> s;
for (int j = 0; j < t; ++j) {
if (s[j] == '0') can[i][j] = 0;
else can[i][j] = 1;
}
}
for (int i = 0; i < n; ++i) {
nxt[i][t] = t;
for (int j = t - 1; j >= 0; --j) {
if (can[i][j] == 0) nxt[i][j] = j;
else nxt[i][j] = nxt[i][j + 1];
}
}
for (int i = 0; i <= t; ++i) {
for (int j = 0; j <= s; ++j) {
dp[i][j] = 1e12;
}
}
dp[t][0] = 0;
vector<vector<ll>> hasil(t, vector<ll>(n + 3, 1e12));
for (int gr = 1; gr <= s; ++gr) {
for (int cur = t - 1; cur >= 0; --cur) {
ll& res = dp[cur][gr];
res = 1e12;
res = min(1ll * res, 1ll * dp[cur + 1][gr - 1] + 1ll * pts[cur] * n);
vector<int> block;
for (int i = 0; i < n; ++i) {
block.push_back(nxt[i][cur]);
}
sort(block.begin(), block.end());
// cout << "LST FOR " << cur << endl;
// for (auto i : block) cout << i << ' ';
// cout << endl;
// for (int i = cur; i < t; ++i) {
// block.push_back(i);
// }
int act = n;
vector<int> vis(n);
int last = -1;
for (auto i : block) {
if (i == t) break;
if (last == -1) last = i;
else {
// puts("TES");
res = min(1ll * res , 1ll * hasil[last][act] - 1ll * (((cur) ? (pre[cur - 1]) : 0)) * act);
// cout << gr << ' ' << act << ' ' << cur << ' ' << i << ' ' << hasil[act][cur] << endl;
// cout << hasil[act][act] - 1ll * (((cur) ? (pre[cur - 1]) : 0)) * act << endl;
}
last = i;
// for (int j = 0; j < n; ++j) {
// if (vis[j]) continue;
// if (nxt[j][i] <= i) {
// vis[j] = 1;
// --act;
// }
// }
--act;
res = min(1ll * res, 1ll * dp[i + 1][gr - 1] + 1ll * (pre[i] - (cur ? (pre[cur - 1]) : 0)) * act);
// cout << "CUR " << cur << endl;
// cout << i << ' ' << act << ' ' << 1ll * rek(i + 1, gr - 1) + 1ll * (pre[i] - (cur ? (pre[cur - 1]) : 0)) * act << endl;
}
if (last != -1) {
res = min(1ll * res, hasil[last][act] - 1ll * (((cur) ? (pre[cur - 1]) : 0)) * act);
// cout << hasil[act][cur] - 1ll * (((cur) ? (pre[cur - 1]) : 0)) * act << endl;
}
// cout << endl;
res = min(1ll * res, 1ll * dp[t][gr - 1] + 1ll * (pre[t - 1] - (cur ? pre[cur - 1] : 0)) * act);
// cout << act << endl;
// return res;
}
hasil = vector<vector<ll>>(t, vector<ll>(n + 3, 1e12));
for (int i = t - 1; i >= 0; --i) {
for (int j = 0; j <= n; ++j) {
if (i < t - 1) hasil[i][j] = hasil[i + 1][j];
hasil[i][j] = min(hasil[i][j], dp[i + 1][gr] + j * pre[i]);
}
}
}
// cout << rek(2, 1) << endl;
// cout << rek(0, 2) << endl;
// for (int i = 1; i <= s; ++i) {
// cout << rek(0, i) << endl;
// }
for (int i = 1; i <= s; ++i) {
cout << dp[0][i] << endl;
}
// cout << rek(0, 0) << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
1640 KB |
Output is correct |
| 2 |
Correct |
35 ms |
1604 KB |
Output is correct |
| 3 |
Correct |
39 ms |
1640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
4568 KB |
Output is correct |
| 2 |
Correct |
256 ms |
6096 KB |
Output is correct |
| 3 |
Correct |
366 ms |
7988 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
40 ms |
1640 KB |
Output is correct |
| 4 |
Correct |
35 ms |
1604 KB |
Output is correct |
| 5 |
Correct |
39 ms |
1640 KB |
Output is correct |
| 6 |
Correct |
205 ms |
4568 KB |
Output is correct |
| 7 |
Correct |
256 ms |
6096 KB |
Output is correct |
| 8 |
Correct |
366 ms |
7988 KB |
Output is correct |
| 9 |
Correct |
459 ms |
12308 KB |
Output is correct |
| 10 |
Correct |
736 ms |
15864 KB |
Output is correct |
| 11 |
Correct |
1504 ms |
34908 KB |
Output is correct |
| 12 |
Correct |
1565 ms |
35912 KB |
Output is correct |
| 13 |
Correct |
1986 ms |
35908 KB |
Output is correct |
| 14 |
Correct |
1678 ms |
35904 KB |
Output is correct |
| 15 |
Correct |
1887 ms |
35944 KB |
Output is correct |
