제출 #787292

#제출 시각아이디문제언어결과실행 시간메모리
787292LuoBoAliens (IOI16_aliens)C++14
25 / 100
143 ms4352 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; const int MAXN=10010; struct node { int x, y; } t[MAXN], p[MAXN]; long long f[MAXN][MAXN]; bool cmp(node x, node y) { return x.x==y.x ? x.y<y.y : x.x<y.x ; } long long sq(long long x) { return x*x; } bool tan_judge(node x, node y, node z) { return ( (double)( ( z.y-y.y ) / ( z.x-y.x ) ) > (double)( ( y.y-x.y ) / ( y.x-x.x ) ) ) ? true : false ; } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i=0; i<n; i++) { t[i].x=r[i]; t[i].y=c[i]; if ( r[i]>c[i] ) swap(t[i].x,t[i].y); } sort(t, t+n, cmp); int right=-1, tt=0; p[0].x=-1; p[0].y=-1; for (int i=0; i<n; i++) { if ( t[i].y<=right ) continue; right=t[i].y; p[++tt]=t[i]; } n=tt; // tt=0; // for (int i=0; i<n; i++) { // if ( tt<=2 ) { t[++tt]=p[i]; continue; } // if ( tan_judge(p[i], t[tt], t[tt-1]) ) t[++tt]=p[i]; // else { // printf("bug! \n"); // while ( tt>2 && !tan_judge(p[i], t[tt], t[tt-1]) ) tt--; // t[++tt]=p[i]; // } // // } // for (int i=0;i<n;i++) printf("%d %d\n",t[i].x,t[i].y); n=tt; long long ans=1e10; for (int i=0;i<=n;i++) for (int opt=0;opt<=k;opt++) f[i][opt]=1e10; f[0][0]=0; for (int i=1; i<=n; i++) { for (int opt=1; opt<=k; opt++) { for (int j=0; j<i; j++) { f[i][opt]=min(f[i][opt], f[j][opt-1] + sq( p[i].y-p[j+1].x+1 ) - sq( max(0, p[j].y-p[j+1].x+1) ) ); } } } for (int opt=1;opt<=k;opt++) ans=min(ans,f[n][opt]); return ans; } /* 5 7 2 0 3 4 4 4 6 4 5 4 6 */
#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...