제출 #1022048

#제출 시각아이디문제언어결과실행 시간메모리
1022048mansurAliens (IOI16_aliens)C++17
25 / 100
2081 ms94548 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define rall(s) s.rbegin(), s.rend() #define all(s) s.begin(), s.end() #define sz(s) (int)s.size() #define s second #define f first using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int N = 2e5 + 5; const ll inf = 1e18; long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { vector<pii> s; for (int i = 0; i < n; i++) { int x = min(r[i], c[i]) + 1; int y = max(r[i], c[i]) + 1; s.push_back({x, y}); } sort(all(s)); int mx[n]; for (int i = 0; i < n; i++) { if (i) mx[i] = mx[i - 1]; else mx[i] = 0; mx[i] = max(mx[i], s[i].s); } ll dp[n + 1][k + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= k; j++) { dp[i][j] = inf; } } dp[0][k] = 0; for (int i = 0; i < n; i++) { int x = (i ? mx[i - 1] : 0); x = max(x, s[i].f - 1); vector<pii> h; for (int j = i; j < n; j++) { h.push_back({s[j].s, j}); } sort(rall(h)); int mn = m + 1, p = n, ok = 1; for (int j = 0; j < sz(h); j++) { if (ok) { ll cost = h[j].f - s[i].f + 1; cost *= cost; //cout << h[j].f << ' ' << s[i].f << " "; cost -= (x - s[i].f + 1) * 1ll * (x - s[i].f + 1); //cout << cost << ' ' << p << ' ' << h[j].s << endl; for (int y = 1; y <= k; y++) { dp[p][y - 1] = min(dp[p][y - 1], dp[i][y] + cost); } } int id = h[j].s; if (id == i) ok = 0; if (s[id].f <= mn) { mn = s[id].f; p = id; } } } ll ans = inf; for (int i = 0; i <= k; i++) ans = min(ans, dp[n][i]); return ans; }
#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...