#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, t, s;
int pts[20005];
int pre[20005];
int nxt[55][20005];
int can[55][20005];
int 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;
int& 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<int>> hasil(t, vector<int>(n + 3, 1e12));
for (int gr = 1; gr <= s; ++gr) {
for (int cur = 0; cur < t; ++cur) {
int& 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(res , 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(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<int>>(t, vector<int>(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 |
4 ms |
8916 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
10212 KB |
Output is correct |
| 2 |
Correct |
40 ms |
10172 KB |
Output is correct |
| 3 |
Correct |
45 ms |
10256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
189 ms |
12932 KB |
Output is correct |
| 2 |
Correct |
339 ms |
14460 KB |
Output is correct |
| 3 |
Correct |
332 ms |
16236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8916 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9172 KB |
Output is correct |
| 3 |
Correct |
46 ms |
10212 KB |
Output is correct |
| 4 |
Correct |
40 ms |
10172 KB |
Output is correct |
| 5 |
Correct |
45 ms |
10256 KB |
Output is correct |
| 6 |
Correct |
189 ms |
12932 KB |
Output is correct |
| 7 |
Correct |
339 ms |
14460 KB |
Output is correct |
| 8 |
Correct |
332 ms |
16236 KB |
Output is correct |
| 9 |
Correct |
462 ms |
20360 KB |
Output is correct |
| 10 |
Correct |
769 ms |
23764 KB |
Output is correct |
| 11 |
Correct |
1465 ms |
41504 KB |
Output is correct |
| 12 |
Correct |
1555 ms |
42744 KB |
Output is correct |
| 13 |
Execution timed out |
2048 ms |
42744 KB |
Time limit exceeded |
| 14 |
Halted |
0 ms |
0 KB |
- |
