제출 #575404

#제출 시각아이디문제언어결과실행 시간메모리
575404handlenameAliens (IOI16_aliens)C++17
60 / 100
1164 ms1048576 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair const int MOD=1e9+7; struct convex{ deque<pair<long long,long long> > dq; long long f(pair<long long,long long> line, long long x){ return line.first*x + line.second; } long long qry(long long x){ while(dq.size()>1){ if(f(dq[0],x)>f(dq[1],x)){ //the next line is better dq.pop_front(); //remove useless line } else break; } return f(dq[0],x); } long double intersect(long long m1, long long c1, long long m2, long long c2){ return (long double)(c2-c1)/(m1-m2); } long double intersect(pair<long long,long long> p1, pair<long long,long long> p2){ return intersect(p1.first,p1.second,p2.first,p2.second); } void ins(long long m,long long c) {//insert line y=mx+c pair<long long,long long> line = make_pair(m,c); while (dq.size()>1) { //to prevent seg fault long long s = dq.size(); if (intersect(dq[s-1], line) <= intersect(dq[s-2], line)){ dq.pop_back(); //removes useless line } else break; } dq.pb(line); } } *conv; pair<int,int> brr[200001]; vector<pair<long long,long long> > arr; long long take_photos(int n,int m,int k,vector<int> r,vector<int> c){ for (int i=0;i<n;i++){ r[i]++; c[i]++; if (r[i]>c[i]) swap(r[i],c[i]); //ri<=ci brr[i].first=r[i]; brr[i].second=c[i]; } sort(brr,brr+n); arr.pb(mp(0,0)); for (int i=0;i<n;i++){ while (arr.back().first==brr[i].first){ arr.pop_back(); } if (brr[i].second>arr.back().second){ arr.pb(brr[i]); } } n=arr.size()-1; long long dp[k+1][n+1]; dp[0][0]=0; for (int j=1;j<=n;j++){ dp[0][j]=1e18; } for (int i=1;i<=k;i++){ dp[i][0]=0; conv=new convex(); for (int j=1;j<=n;j++){ dp[i][j]=1e18; long long grad=(1-arr[j].first)*2; long long add=dp[i-1][j-1]+(arr[j].first-1)*(arr[j].first-1); if (arr[j].first<=arr[j-1].second){ add-=(arr[j-1].second-arr[j].first+1)*(arr[j-1].second-arr[j].first+1); } conv->ins(grad,add); dp[i][j]=conv->qry(arr[j].second); dp[i][j]+=arr[j].second*arr[j].second; dp[i][j]=min(dp[i][j],dp[i-1][j]); } } return dp[k][n]; }
#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...