제출 #923735

#제출 시각아이디문제언어결과실행 시간메모리
923735velislavgarkovAliens (IOI16_aliens)C++14
0 / 100
1 ms2796 KiB
#include "aliens.h" #include <iostream> #include <algorithm> #include <vector> using namespace std; const int MAXN=1e5+10; const long long INF=1e16; struct Interval { int l; int r; bool friend operator < (Interval a, Interval b) { if (a.l==b.l) return a.r>b.r; return a.l<b.l; } }; Interval b[MAXN]; vector <Interval> a; vector <long long> dp[MAXN]; long long take_photos(int n, int m, int k, vector <int> r, vector <int> c) { for (int i=0;i<n;i++) { b[i].l=min(r[i],c[i]); b[i].r=max(r[i],c[i]); } sort(b,b+n); int maxr=b[0].r; a.push_back({0,0}); a.push_back(b[0]); for (int i=1;i<n;i++) { if (b[i].r<=maxr) continue; a.push_back(b[i]); maxr=max(maxr,b[i].r); } n=a.size()-1; for (int i=0;i<=n;i++) dp[i].resize(k); long long dif; dp[0][0]=0; for (int i=1;i<=n;i++) { for (int j=1;j<=min(i,k);j++) { dp[i][j]=INF; for (int p=i;p>0;p--) { dif=a[i].r-a[p].l+1; dp[i][j]=min(dp[i][j],dp[p-1][j-1]+dif*dif); } } } return dp[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...