Submission #1082674

#TimeUsernameProblemLanguageResultExecution timeMemory
1082674_callmelucianPopeala (CEOI16_popeala)C++14
100 / 100
540 ms6996 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef tuple<int,int,int> tt; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const int mn = 2e4 + 4; int dp[2][mn], opt[55][mn], pts[mn], pre[mn]; bool solved[55][mn]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, T, S; cin >> n >> T >> S; for (int i = 1; i <= T; i++) { cin >> pts[i]; pre[i] = pre[i - 1] + pts[i]; } for (int i = 1; i <= n; i++) { string s; cin >> s; for (int j = 1; j <= T; j++) solved[i][j] = (s[j - 1] == '1'); } for (int j = 1; j <= T; j++) dp[0][j] = INT_MAX; for (int sub = 1; sub <= S; sub++) { int t = sub & 1; for (int j = 0; j <= T; j++) dp[t][j] = INT_MAX; for (int score = 0; score <= n; score++) opt[score][0] = dp[t ^ 1][0]; vector<pii> order; for (int i = 1; i <= n; i++) order.emplace_back(i, 0); for (int j = 1; j <= T; j++) { vector<pii> tmp; for (pii it : order) { int row, col; tie(row, col) = it; if (!solved[row][j]) tmp.emplace_back(row, j); } for (pii it : order) { int row, col; tie(row, col) = it; if (solved[row][j]) tmp.emplace_back(row, col); } order = tmp; for (int block = 0, low = j; block <= n && low; block++) { int score = n - block; if (opt[score][low - 1] != INT_MAX) dp[t][j] = min(dp[t][j], opt[score][low - 1] + pre[j] * score); if (block < n) low = order[block].second; } if (dp[t ^ 1][j] == INT_MAX) for (int score = 0; score <= n; score++) opt[score][j] = opt[score][j - 1]; else for (int score = 0; score <= n; score++) opt[score][j] = min(opt[score][j - 1], dp[t ^ 1][j] - pre[j] * score); } cout << dp[t][T] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...