제출 #934588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
934588		Lib	Aliens (IOI16_aliens)	C++14	0 / 100	1 ms	348 KiB

aliens

#include <bits/stdc++.h>
#include <aliens.h>
//Aliens - DnC 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)
vector <vector <long long> > DP;
//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;
//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-(pow/2));
}

void DNC(int SubtreeLRange, int SubtreeRRange, int SubtreeLBound, int SubtreeRBound, int CurPics){
	if(SubtreeLRange>SubtreeRRange){
		return;
	}
	int mid=SubtreeLRange+SubtreeRRange;
	int OptPoint;
	long long CCost;
	mid/=2;
	for(int i=SubtreeLBound;i<=SubtreeRBound&&i<mid;i++){
		CCost=DP[i][CurPics-1]+binpow(ActualSegments[mid].End-ActualSegments[i+1].Start,2)-binpow(max(0ll,ActualSegments[i+1].Start-ActualSegments[i].End),2);
		if(CCost<DP[mid][CurPics]){
			DP[mid][CurPics]=CCost;
			OptPoint=i;
		}
	}
	DNC(SubtreeLRange,mid-1,SubtreeLBound,OptPoint, CurPics);
	DNC(mid+1,SubtreeRRange,OptPoint,SubtreeRBound, CurPics);
}
long long take_photos(int N,int M, int Pics, vector <int> Rows, vector <int> Columns){
  for(int i=1;i<=N+1;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});
  N=ActualSegments.size();
  Pics=min(Pics,N);
  //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]);
    }
  }
  DP.resize(N+3,vector <long long>(Pics+3,0));
  //Now, the DP.
  /*
  Knuth opt is retarded so I opt to DnC. Strictly stronger and easier to implement. Will code first then comment later eventually
  */
  long long ThisSplit;
  long long ThisPic;
  long long Overlap;
  long long Ans=INF;
  for(int i=1;i<=N;i++){
  	for(int k=2;k<=Pics;k++){
  		DP[i][k]=INF;
  		DP[0][k]=0;
	  }
	  DP[i][0]=0;
  }
  for(int i=1;i<=N;i++){
  	  DP[i][1]=binpow(ActualSegments[i].End-ActualSegments[1].Start,2);
  }
  Ans=INF;
  for(int i=2;i<=Pics;i++){
      DNC(1,N,0,N,i);
  }
  return N;
  for(int i=1;i<=Pics;i++){
  	Ans=min(Ans,DP[N][i]);
  }
  return Ans;
}

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

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:71:13: warning: unused variable 'ThisSplit' [-Wunused-variable]
   71 |   long long ThisSplit;
      |             ^~~~~~~~~
aliens.cpp:72:13: warning: unused variable 'ThisPic' [-Wunused-variable]
   72 |   long long ThisPic;
      |             ^~~~~~~
aliens.cpp:73:13: warning: unused variable 'Overlap' [-Wunused-variable]
   73 |   long long Overlap;
      |             ^~~~~~~
aliens.cpp: In function 'void DNC(int, int, int, int, int)':
aliens.cpp:49:5: warning: 'OptPoint' may be used uninitialized in this function [-Wmaybe-uninitialized]
   49 |  DNC(SubtreeLRange,mid-1,SubtreeLBound,OptPoint, CurPics);
      |  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40