Submission #531742

#	Time	Username	Problem	Language	Result	Execution time	Memory
531742		mosiashvililuka	Aliens (IOI16_aliens)	C++14	25 / 100	1090 ms	1048580 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,M,k,pi,pr[1000009],pas;
long long bofx[1000009];
pair <long long, long long> p[1000009],pp[1000009];
vector <vector <long long> > dp;
long long take_photos(int Nn, int Mm, int Kk, std::vector<int> Rr, std::vector<int> Cc) {
	M=Nn;a=Mm;k=Kk;
	dp.resize(a+3);
	for(i=0; i<a+3; i++){
		dp[i].resize(min(k,a)+3);
	}
	for(i=1; i<=M; i++){
		if(Rr[i-1]>Cc[i-1]) swap(Rr[i-1],Cc[i-1]);
		pp[i]={Rr[i-1]+1,-Cc[i-1]-1};
	}
	sort(pp+1,pp+M+1);
	for(i=1; i<=M; i++) pp[i].second=-pp[i].second;
	for(i=1; i<=M; i++){
		if(pi!=0&&p[pi].second>=pp[i].second){
			
		}else{
			pi++;p[pi]=pp[i];
		}
	}
	/*cout<<"rewrew "<<pi<<"\n";
	for(i=1; i<=pi; i++) cout<<p[i].first<<" "<<p[i].second<<"\n";*/
	for(i=1; i<=pi; i++){
		pr[p[i].first]=p[i].second;
		bofx[p[i].second]=p[i].first;
	}
	for(i=1; i<=a; i++){
		pr[i]=max(pr[i],pr[i-1]);
	}
	for(i=0; i<=a+1; i++){
		for(j=0; j<=min(k,a)+1; j++){
			dp[i][j]=a*a+3;
		}
	}
	dp[0][0]=0;
    for(i=1; i<=a; i++){
    	for(j=1; j<=min(i,k); j++){
    		if(bofx[i]==0){
    			dp[i][j]=dp[i-1][j];
    			continue;
			}
    		dp[i][j]=i*i;
    		for(ii=0; ii<i; ii++){
    			//zx=i*i+i*(-2*ii)+(dp[pr[ii]][j-1]-pr[ii]*pr[ii]+2*pr[ii]*ii);
    			if(pr[ii]>ii){
    				zx=(i-ii)*(i-ii)+dp[pr[ii]][j-1]-(pr[ii]-ii)*(pr[ii]-ii);
				}else{
					zx=(i-ii)*(i-ii)+dp[pr[ii]][j-1];
				}
    			dp[i][j]=min(dp[i][j],zx);
			}
		}
	}
	pas=dp[a][1];
	for(j=1; j<=min(a,k); j++){
		pas=min(pas,dp[a][j]);
	}
	return pas;
}

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