Submission #1114895

#TimeUsernameProblemLanguageResultExecution timeMemory
1114895mat_jurAliens (IOI16_aliens)C++17
0 / 100
1 ms516 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #ifdef DEBUG auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";} #define debug(X) cerr << "["#X"]: " << X << '\n'; #else #define cerr if(0)cout #define debug(X) ; #endif using ll = long long; #define all(v) (v).begin(), (v).end() #define ssize(x) int(x.size()) #define fi first #define se second #define mp make_pair #define eb emplace_back ll sq(int x) { return ll(x)*x; } long long take_photos(int n, int m, int k, std::vector<int> x, std::vector<int> y) { for (int i = 0; i < n; ++i) if (x[i] > y[i]) swap(x[i], y[i]); debug(x); debug(y); vector<int> nx, ny; vector<int> idx(n); iota(all(idx), 0); sort(all(idx), [&](int a, int b) { return mp(y[a], x[a]) > mp(y[b], x[b]); }); debug(idx); int mx = m+1; for (int i : idx) { if (mx <= x[i]) continue; debug(i); debug(mx); debug(mp(x[i], y[i])); nx.eb(x[i]); ny.eb(y[i]); mx = x[i]; } n = ssize(nx); x = nx; y = ny; reverse(all(x)); reverse(all(y)); debug(n); debug(x); debug(y); const ll inf = 1e15; debug(inf); vector<vector<ll>> dp(n+1, vector<ll>(k+1, inf)); dp[0][0] = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= k; ++j) { for (int l = 0; l < i; ++l) { dp[i][j] = min(dp[i][j], dp[l][j-1] + sq(y[i-1] - x[l] + 1) - (l - 1 >= 0 ? sq(max(0, y[l-1] - x[l]+1)) : 0ll) ); } } } debug(dp); return dp[n][k]; } #ifdef LOCAL int main() { int n, m, k; assert(3 == scanf("%d %d %d", &n, &m, &k)); std::vector<int> r(n), c(n); for (int i = 0; i < n; i++) { assert(2 == scanf("%d %d", &r[i], &c[i])); } long long ans = take_photos(n, m, k, r, c); printf("%lld\n", ans); } #endif
#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...