Submission #310073

#TimeUsernameProblemLanguageResultExecution timeMemory
310073jungsnowPopeala (CEOI16_popeala)C++14
26 / 100
1577 ms47096 KiB
#include<bits/stdc++.h> using namespace std; int n, s, t, c[4001]; int cn[4001][4001], sum[4001]; int dp[4001][55]; bool a[55][4001]; int main() { // freopen("popeala.inp", "r", stdin); // freopen("popeala.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>t>>s; for (int i = 1; i <= t; ++i) cin>>c[i], sum[i] = c[i] + sum[i - 1]; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= t; ++j) { char x; cin>>x; a[i][j] = x - '0'; } } int has[55]; for (int r = 1; r <= t; ++r) { memset(has, 0, sizeof has); for (int l = r; l >= 1; --l) { for (int i = 1; i <= n; ++i) { has[i] += a[i][l]; cn[l][r] += (has[i] == r - l + 1); } } } memset(dp, 0x3f, sizeof dp); dp[0][0] = 0; for (int r = 1; r <= t; ++r) { for (int l = 1; l <= r; ++l) { for (int k = 1; k <= s; ++k) { dp[r][k] = min(dp[r][k], cn[l][r] * (sum[r] - sum[l - 1]) + dp[l - 1][k - 1]); } } } for (int k = 1; k <= s; ++k) cout<<dp[t][k]<<'\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...