# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
427524 | 2021-06-14T16:29:35 Z | InternetPerson10 | Aliens (IOI16_aliens) | C++17 | 1 ms | 204 KB |
#include "aliens.h" #include <bits/stdc++.h> typedef long long ll; using namespace std; vector<pair<int, int>> ps; vector<pair<int, int>> pso; ll dp[4001][4001]; ll DP(int n, int k) { if(dp[n][k] > -1) return dp[n][k]; ll ans = 99999999999999999; if(k == 0) { if(n == 0) return dp[n][k] = 0; return dp[n][k] = ans; } ll x = 0; for(int i = n-1; i >= k-1; i--) { x += (ll)(pso[n].second - pso[i].second) * (pso[i+1].first - pso[i].first); ans = min(ans, DP(i, k-1) + x); } return ans; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { swap(m, n); ps.resize(m); for(int i = 0; i < m; i++) { if(r[i] > c[i]) ps[i] = {c[i], r[i]}; else ps[i] = {r[i], c[i]}; } sort(ps.begin(), ps.end()); int best = n+1; for(int i = m-1; i >= 0; i--) { // cout << ps[i].first << ' ' << ps[i].second << '\n'; if(i == m-1) pso.push_back({-1, -1}); if(ps[i].first == pso.back().first) continue; if(i == m-1) pso.pop_back(); if(ps[i].second < best) { pso.push_back(ps[i]); best = ps[i].second; } } reverse(pso.begin(), pso.end()); for(int i = 0; i <= pso.size(); i++) { for(int j = 0; j <= k; j++) { dp[i][j] = -1; } } for(int i = 0; i < pso.size(); i++) cout << pso[i].first << ' ' << pso[i].second << '\n'; ll ans = max(pso[pso.size()-1].first, pso[pso.size()-1].second) - min(pso[0].first, pso[0].second) + 1; ans *= ans; return ans - 2 * DP(pso.size() - 1, k-1); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | Wrong secret! |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | Wrong secret! |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | Wrong secret! |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | Wrong secret! |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | Wrong secret! |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 204 KB | Wrong secret! |
2 | Halted | 0 ms | 0 KB | - |