제출 #130040

#제출 시각아이디문제언어결과실행 시간메모리
130040MvCAliens (IOI16_aliens)C++11
60 / 100
2012 ms6136 KiB
#pragma GCC target("avx2") #pragma GCC optimization("O3") #pragma GCC optimization("unroll-loops") #include<bits/stdc++.h> #include "aliens.h" #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<62); const int inf=(1<<30); const int nmax=1e5+50; const int mod=1e9+7; using namespace std; int n,m,k,i,j,t,id,x,y; ll f[2][nmax]; pair<int,int>pr[nmax],v[nmax]; ll cst(int l,int r) { ll x=v[r].sc-v[l].fr; ll y=max(0,v[l-1].sc-v[l].fr); return x*x-y*y; } void rec(int l,int r,int opl,int opr) { if(l>r)return; int mid=(l+r)/2,bst; for(int i=opl;i<=min(mid,opr);i++) { if(f[0][i-1]+cst(i,mid)<=f[1][mid]) { f[1][mid]=f[0][i-1]+cst(i,mid); bst=i; } } rec(l,mid-1,opl,bst); rec(mid+1,r,bst,opr); } ll take_photos(int N,int M,int K,vector<int>r,vector<int>c) { n=N,m=M,k=K; for(i=1;i<=n;i++) { pr[i].fr=min(r[i-1],c[i-1]); pr[i].sc=max(r[i-1],c[i-1])+1; } for(j=1;j<=n;j++)f[0][j]=f[1][j]=llinf; sort(pr+1,pr+n+1); int mx=-1; for(i=1;i<=n;i++) { if(pr[i].sc>mx)v[++id]=mkp(pr[i].fr,mx=pr[i].sc); } n=id; k=min(k,n); for(i=1;i<=k;i++) { rec(1,n,1,n); for(j=1;j<=n;j++) { f[0][j]=f[1][j]; f[1][j]=llinf; } } return f[0][n]; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
aliens.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")
 
aliens.cpp: In function 'void rec(int, int, int, int)':
aliens.cpp:43:5: warning: 'bst' may be used uninitialized in this function [-Wmaybe-uninitialized]
  rec(l,mid-1,opl,bst);
  ~~~^~~~~~~~~~~~~~~~~
#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...