Submission #330555

#TimeUsernameProblemLanguageResultExecution timeMemory
330555IgorIAliens (IOI16_aliens)C++17
12 / 100
248 ms2412 KiB
#include <bits/stdc++.h> #include "aliens.h" using namespace std; long long take_photos(int n, int m, int k, vector<int> l, vector<int> r) { vector<int> cv(m); for (int i = 0; i < m; i++) { cv[i] = i + 1; } for (int i = 0; i < n; i++) { int x = min(l[i], r[i]); int y = max(l[i], r[i]); cv[y] = min(cv[y], x); } l.clear(); r.clear(); for (int i = 0; i < m; i++) { if (cv[i] <= i) l.push_back(cv[i]), r.push_back(i); } n = l.size(); const long long INFLL = 1e18; vector<vector<long long> > dp(n + 1, vector<long long>(k + 1, INFLL)); dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int g = 0; g < k; g++) { for (int p = 0; p < i; p++) { int L = l[p], R = r[i - 1]; int covto = -1; if (p) covto = r[p - 1]; if (covto < L) dp[i][g + 1] = min(dp[i][g + 1], dp[p][g] + 1ll * (R - L + 1) * (R - L + 1)); else dp[i][g + 1] = min(dp[i][g + 1], dp[p][g] + 1ll * (R - L + 1) * (R - L + 1) - 1ll * (covto - L + 1) * (covto - L + 1)); //cout << p << " " << i << " " << g + 1 << " " << dp[i][g + 1] << endl; } //cout << i << " " << g + 1 << " " << dp[i][g + 1] << endl; } } return *min_element(dp[n].begin(), dp[n].end()); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...