Submission #598369

#TimeUsernameProblemLanguageResultExecution timeMemory
5983691binPopeala (CEOI16_popeala)C++14
0 / 100
20 ms2644 KiB
#include <bits/stdc++.h> using namespace std; #define all(v) v.begin(), v.end() typedef long long ll; const int MAX = 2e4 + 5; int n, t, s, dp[55][MAX], p[MAX], chk[55][MAX], bf[55][MAX], ix[MAX][55], pf[MAX]; string w; int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> t >> s; for(int i = 1; i <= t; i++) cin >> p[i], pf[i] = pf[i - 1] + p[i]; for(int i = 0; i < n; i++){ cin >> w; for(int j = 0; j < t; j++) chk[i + 1][j + 1] = w[j] - '0'; } for(int i = 1; i <= n; i++) for(int j = 1; j <= t; j++){ bf[i][j] = (chk[i][j] ? bf[i][j - 1] : j); ix[j][i - 1] = bf[i][j]; } for(int i = 1; i <= t; i++) sort(ix[i], ix[i] + n); for(int j = 1; j <= t; j++) for(int i = 1; i <= n; i++) if(!bf[i][j]) dp[1][j] += pf[j]; cout << dp[1][t] << '\n'; for(int i = 2; i <= s; i++){ for(int j = i; j <= t; j++){ dp[i][j] = dp[i - 1][j - 1] + (pf[j] - pf[j - 1]) * n; for(int k = 0; k < n; k++){ if(ix[j][k] >= i) dp[i][j] = min(dp[i][j], dp[i - 1][ix[j][k] - 1] + (pf[j] - pf[ix[j][k] - 1]) * k); } //cout << dp[i][j] << ' '; } //cout << '\n'; cout << dp[i][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...