제출 #33786

#제출 시각아이디문제언어결과실행 시간메모리
33786leejseoAliens (IOI16_aliens)C++11
0 / 100
0 ms394212 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long lld; #define append push_back #define MAXN 100001 #define all(v) (v).begin(), (v).end() long long D[MAXN][501]; struct Point{ int r, c; } A[MAXN]; long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { // n : interesting place // m : row // k : max image vector <Point> arr; for (int i = 0; i < n; i ++) arr.append({min(r[i], c[i]), max(r[i], c[i])}); sort(all(arr), [](const Point &a, const Point &b){ if (a.c != b.c) return a.c < b.c; return a.r > b.r; }); int K = min(k, n); for (int i=1; i <= n; i++) for(int j=1; j<=K; j++) D[i][j] = 1e18; for (int i=1; i<=n; i++) D[i][1] = (long long )(A[i].c - A[1].r+1 )*(A[i].c - A[1].r+1); for (int i=2; i<K; i++){ for(int j=1; j<n; j++) for (int k=j+1; k<=n; k++){ long long v = D[j][i] + (long long)(A[k].c - A[j+1].r+1)*(A[k].c - A[j+1].r+1); if (A[j+1].r <= A[j].c) v -= (long long)(A[j].c - A[j+1].r+1)*(A[k].c-A[j+1].r+1); D[k][i+1] = min(D[k][i+1], v); } } return D[n][K]; }
#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...