Submission #963720

#TimeUsernameProblemLanguageResultExecution timeMemory
963720LucaIliePopeala (CEOI16_popeala)C++17
26 / 100
2048 ms10660 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 50; const int MAX_T = 50000; const int MAX_S = 50; const long long INF = 1e15; bool solved[MAX_N][MAX_T + 1]; int points[MAX_T + 1], last0[MAX_N][MAX_T + 1]; long long dp[MAX_T + 1][MAX_S + 1], solvers[MAX_T + 1]; int main() { int n, t, s; cin >> n >> t >> s; for ( int i = 1; i <= t; i++ ) { cin >> points[i]; points[i] += points[i - 1]; } for ( int j = 0; j < n; j++ ) { for ( int i = 1; i <= t; i++ ) { char ch; cin >> ch; solved[j][i] = ch - '0'; last0[j][i] = (!solved[j][i] ? i : last0[j][i]); solvers[i] += ((long long)solved[j][i] << j); } } for ( int i = 0; i <= t; i++ ) { for ( int k = 0; k <= s; k++ ) dp[i][k] = INF; } dp[0][0] = 0; for ( int i = 1; i <= t; i++ ) { vector<int> pos; for ( int j = 0; j < n; j++ ) pos.push_back( last0[j][i] ); sort( pos.begin(), pos.end() ); reverse( pos.begin(), pos.end() ); long long mask = (1LL << n) - 1; for ( int j = i - 1; j >= 0; j-- ) { mask &= solvers[j + 1]; int c = 0; for ( int i = 0; i < n; i++ ) c += ((mask >> i) & 1); for ( int k = 1; k <= s; k++ ) dp[i][k] = min( dp[i][k], dp[j][k - 1] + (long long)c * (points[i] - points[j]) ); } } for ( int k = 1; k <= s; k++ ) cout << dp[t][k] << "\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...