| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 937406 | Lib | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "aliens.h"
//Aliens - CHT variant
using namespace std;
//long long DP[6000][6000]; //dp[i][k]: Minimum cost for covering the first i segments with EXACTLY k pictures (obviously i>=k)
//nvm switched back into at most k isntead of exactly k. Doesn't matter much since we would always want to take
//as many pics as possible anyways
vector <vector <long long> > DP;
long long M;
int N;
//Why tf are there segments here? Refer to the official editorial for that - the expaination seems good enough
const long long INF=2000000000000000000;
struct seg{
long long Start;
long long End;
};
seg Segments[200003];
vector <seg> ActualSegments;
vector <seg> CorrespondingRange;
//Custom sort function for removing uneeded segments. If a segment which starts at L and end at R is kept, alongside with another segment which starts at L' and end as R', and L'<= L <= R <= R' (aka: The segment is completely covered), the DP will become absolute shitfuckery and extremely wrong (trust me, I thought it would work but it didn't)
bool operator< (const seg &x, const seg &y){
if(x.Start==y.Start){
return x.End>y.End;
}else{
return x.Start<y.Start;
}
}
//Binpow template for non-shitty squaring
long long binpow(long long x, long long pow){
if(pow==1){
return x;
}
if(pow==0){
return 1;
}
return binpow(x,pow/2)*binpow(x,(pow+1)/2);
}
//Define lines type
struct Lines{
//form: y=ax+b, where x will eventually be the endpoint coordinate of a segment
long long Slopes; //a
long long Extras; //b
};
vector <Lines> CurrentConvexHull; //Forming the corresponding convexhull for k-th layer (the entirely of dp[i][k])
vector <Lines> PreviousConvexHull; //Each layer of k has a corresponding convex hull. dp[i][k] is calculated
//based on the corresponding convex hull of the k-1th layer
void CalcDP(int k){
CurrentConvexHull.clear();
CorrespondingRange.clear(); //Calculating: For the i-th line in the prev convex hull, in which range of values will it
//yield the min value?
CorrespondingRange.push_back({-1.-1});
int LeftIntersection, RightIntersection
for(int i=1;i<PreviousConvexHull.size()-1;i++){
}
if(k==1){
for(int i=1;i<=N;i++){
DP[i][k]=binpow(ActualSegments[i].End-ActualSegments[1].Start,2);
}
}
PreviousConvexHull=CurrentConvexHull;
}
long long take_photos(int n,int m, int Pics, vector <int> Rows, vector <int> Columns){
for(int i=1;i<=N;i++){
Segments[i]={min(Rows[i-1],Columns[i-1])+1,max(Rows[i-1],Columns[i-1])+1};
}
sort(Segments+1,Segments+N+1);
ActualSegments.push_back({0,0});
//Removing the fully-covered segments: It is easy to see that our resulting set of segments will have the later segments have both higher start and endpoints when compared to all previous ones, so...... Again, if you can't understand this, you shouldn't try learning about fucking ALIENS' TRICK just yet.
for(int i=1;i<=N;i++){
if(Segments[i].End>ActualSegments.back().End){
ActualSegments.push_back(Segments[i]);
}
}
N=ActualSegments.size()-1;
Pics=min(Pics,N);
DP.resize(N+3,vector <long long>(Pics+3,0));
//Now, the DP.
long long Ans=INF;
for(int i=1;i<=N;i++){
DP[i][0]=INF;
}
for(int k=1;k<=Pics;k++){
DP[0][k]=INF;
}
Ans=INF;
for(int i=1;i<=Pics;i++){
CalcDP(i);
}
for(int i=1;i<=Pics;i++){
Ans=min(Ans,DP[N][i]);
}
return Ans;
}