Submission #1111165

#TimeUsernameProblemLanguageResultExecution timeMemory
1111165Ghulam_JunaidPopeala (CEOI16_popeala)C++17
26 / 100
2049 ms9040 KiB
#include <bits/stdc++.h> using namespace std; const int T = 2e4 + 10; const int N = 52; const int S = 52; int t, n, s, points[T], pref[T], dp[T][S]; int mat[N][T], perf_mat[N][T], maxl[N][T]; int good(int l, int r){ int ans = 0; for (int i=1; i<=n; i++) ans += ((perf_mat[i][r] - perf_mat[i][l - 1]) == (r - l + 1)); return ans; } int main(){ cin >> n >> t >> s; for (int i=1; i<=t; i++) cin >> points[i], pref[i] = pref[i - 1] + points[i]; for (int i=1; i<=n; i++){ for (int j=1; j<=t; j++){ char c; cin >> c; mat[i][j] = (c - '0'); perf_mat[i][j] = mat[i][j] + perf_mat[i][j - 1]; } } for (int l=1; l<=t; l++){ int cnt = good(l, t); int summ = pref[t] - pref[l - 1]; dp[l][1] = cnt * summ; // cout << l << " 1 : " << dp[l][1] << endl; } for (int i=1; i<=n; i++){ maxl[i][t + 1] = t + 1; for (int j = t; j > 0; j--){ maxl[i][j] = maxl[i][j + 1]; if (!mat[i][j]) maxl[i][j] = j; } } vector<int> inds; for (int subs = 2; subs <= s; subs++){ for (int l = 1; l <= t; l++){ if ((t - l + 1) < subs) continue; inds.clear(); for (int i=1; i<=n; i++) inds.push_back(maxl[i][l]); sort(inds.begin(), inds.end()); int p1 = 0; dp[l][subs] = 2e9; for (int r = l + 1; r <= t; r++){ if ((t - r + 1) < (subs - 1)) continue; while (p1 < n && inds[p1] < r) p1++; dp[l][subs] = min(dp[l][subs], dp[r][subs - 1] + (n - p1) * (pref[r - 1] - pref[l - 1])); } // dp[l][subs] = dp[l + 1][subs - 1] + good(l, l) * points[l]; // cout << "init = " << dp[l][subs] << endl; // int rem = n; // for (int x : inds){ // int r = x + 1; // rem--; // if ((t - r + 1) < (subs - 1)) // continue; // dp[l][subs] = min(dp[l][subs], dp[r][subs - 1] + rem * (pref[r - 1] - pref[l - 1])); // } // cout << l << " " << subs << " : " << dp[l][subs] << endl; } } for (int i=1; i<=s; i++) cout << dp[1][i] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...