Submission #976484

#TimeUsernameProblemLanguageResultExecution timeMemory
976484duckindogPopeala (CEOI16_popeala)C++17
100 / 100
267 ms12312 KiB
#include <bits/stdc++.h> using namespace std; const int N = 50 + 10, T = 20'000 + 10; int n, t, s; int point[T], d[T]; bool b[T][N]; int last[T][N]; int f[N][T]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> t >> s; for (int i = 1; i <= t; ++i) cin >> point[i]; for (int i = 1; i <= n; ++i) { string s; cin >> s; for (int j = 1; j <= t; ++j) b[j][i] = (s[j - 1] == '1'); } for (int i = 1; i <= t; ++i) d[i] = d[i - 1] + point[i]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= t; ++j) last[j][i] = (!b[j][i] ? j : last[j - 1][i]); } for (int i = 1; i <= t; ++i) { last[i][0] = i; sort(last[i], last[i] + n + 1); } memset(f, 127, sizeof f); f[0][0] = 0; for (int i = 1; i <= s; ++i) { vector<int> best(n + 1, 2'000'000'000); for (int j = 1; j <= t; ++j) { for (int cnt = 0; cnt <= n; ++cnt) { for (int it = last[j - 1][cnt]; it < last[j][cnt]; ++it) best[cnt] = min(best[cnt], f[i - 1][it] - cnt * d[it]); f[i][j] = min(f[i][j], best[cnt] + cnt * d[j]); } } } for (int i = 1; i <= s; ++i) cout << f[i][t] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...