Submission #923750

#TimeUsernameProblemLanguageResultExecution timeMemory
923750velislavgarkovAliens (IOI16_aliens)C++14
12 / 100
105 ms4700 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=b[i].r; } n=a.size()-1; k=min(n,k); for (int i=0;i<=n;i++) dp[i].resize(k+1); long long dif; dp[0][0]=0; for (int i=1;i<=n;i++) { dp[i][0]=INF; for (int j=1;j<=k;j++) { dp[i][j]=dp[i][j-1]; for (int p=i;p>=1;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...