제출 #786496

#제출 시각아이디문제언어결과실행 시간메모리
786496hcngAliens (IOI16_aliens)C++14
25 / 100
2069 ms28756 KiB
#include <bits/stdc++.h> #include "aliens.h" using namespace std; #define long long long struct Point { long r; long c; } p[50005], a[50005]; long maxc, plen; long dp[4005][50005]; long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (long i = 0; i < n; i++) { if (r[i] > c[i]) swap(r[i], c[i]); p[i].r = r[i]; p[i].c = c[i]; } sort(p, p + n, [](const Point &a, const Point &b) { return a.r < b.r || (a.r == b.r && a.c < b.c); } ); maxc = -1, plen = 0; a[0].r = -100, a[0].c = -100; for (long i = 0; i < n; i++) { if (p[i].c > maxc) { maxc = p[i].c; a[++plen] = p[i]; } } n = plen; for (long i = 0; i <= k; i++) for (long j = 0; j <= n; j++) dp[i][j] = 1e15; dp[0][0] = 0; long ans = 1e15; for (long i = 1; i <= k; i++) { for (long j = 1; j <= n; j++) { for (long x = 0; x < j; x++) { dp[i][j] = min(dp[i][j], dp[i - 1][x] + (a[j].c - a[x + 1].r + 1) * (a[j].c - a[x + 1].r + 1) - max(0ll, a[x].c - a[x + 1].r + 1) * max(0ll, a[x].c - a[x + 1].r + 1)); } } ans = min(ans, dp[i][n]); } 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...