Submission #537114

#TimeUsernameProblemLanguageResultExecution timeMemory
537114maomao90Popeala (CEOI16_popeala)C++17
8 / 100
57 ms872 KiB
// Hallelujah, praise the one who set me free // Hallelujah, death has lost its grip on me // You have broken every chain, There's salvation in your name // Jesus Christ, my living hope #include <bits/stdc++.h> using namespace std; template <class T> inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;} template <class T> inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;} #define REP(i, s, e) for (int i = s; i < e; i++) #define RREP(i, s, e) for (int i = s; i >= e; i--) typedef long long ll; typedef long double ld; #define MP make_pair #define FI first #define SE second typedef pair<int, int> ii; typedef pair<ll, ll> pll; #define MT make_tuple typedef tuple<int, int, int> iii; #define ALL(_a) _a.begin(), _a.end() #define pb push_back typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; #ifndef DEBUG #define cerr if (0) cerr #endif #define INF 2000000005 #define LINF 1000000000000000005ll #define MAXT 20005 #define MAXN 55 int n, t, s; int p[MAXT]; char g[MAXT][MAXN]; uint dp[MAXN][MAXT]; int best[MAXN], last[MAXN], ac[MAXT]; int main() { #ifndef DEBUG ios::sync_with_stdio(0), cin.tie(0); #endif cin >> n >> t >> s; REP (i, 1, t + 1) { cin >> p[i]; p[i] += p[i - 1]; } REP (i, 1, n + 1) { REP (j, 1, t + 1) { cin >> g[i][j]; } } REP (i, 1, t + 1) { dp[0][i] = INF; } REP (i, 1, s + 1) { REP (j, 0, n + 1) { best[j] = 0; last[j] = 0; } ac[0] = n; dp[i][0] = INF; REP (j, 1, t + 1) { dp[i][j] = INF; ac[j] = n; auto cost = [&] (int x) { return dp[i - 1][x] + (p[j] - p[x]) * n; }; if (cost(best[n]) > cost(j - 1)) { best[n] = j - 1; } REP (k, 1, n + 1) { if (g[k][j] == '0') { REP (l, last[k] + 1, j + 1) { best[ac[l]] = 0; } REP (l, last[k] + 1, j + 1) { ac[l]--; auto cost = [&] (int x) { return dp[i - 1][x] + (p[j] - p[x]) * ac[l]; }; if (cost(best[ac[l]]) > cost(l - 1)) { best[ac[l]] = l - 1; } cerr << l << ' ' << ac[l] << '\n'; } last[k] = j; } } if (j < i) continue; REP (k, 0, n + 1) { cerr << ' ' << k << ' ' << best[k] << '\n'; mnto(dp[i][j], dp[i - 1][best[k]] + (p[j] - p[best[k]]) * ac[best[k] + 1]); } cerr << i << ' ' << j << ": " << dp[i][j] << '\n'; } } REP (i, 1, s + 1) { 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...