Submission #1291772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291772		enzy	Carnival Tickets (IOI20_tickets)	C++20	41 / 100	594 ms	93164 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1510;
const int maxn=82;
const ll inf=1e14;
int ma[MAXN], me[MAXN], id_me[MAXN], id_ma[MAXN];
int v[MAXN][MAXN];
ll dp[MAXN][MAXN], alt[maxn][2*maxn*maxn];
vector<int>grande[MAXN], pequeno[MAXN];
ll solve2(int n, int m){
	vector<vector<int>>ans(n,vector<int>(m,-1));
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++) dp[i][j]=-inf;
	dp[0][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=n;j++){
			int k=i-j;
			if(j) dp[j][k]=max(dp[j][k],dp[j-1][k]-me[i]);
			if(k) dp[j][k]=max(dp[j][k],dp[j][k-1]+ma[i]);
		}
	}
	int a=n/2, b=n/2;
	while(a+b){
		if(!a){ // tenho q pegar o maior
			ans[a+b-1][m-1]=0;
			b--;
		}else if(!b){ // tenho q pegar o menor
			ans[a+b-1][0]=0;
			a--;
		}else if(dp[a-1][b]-me[a+b]==dp[a][b]){
			ans[a+b-1][0]=0;
			a--;
		}else{
			ans[a+b-1][m-1]=0;
			b--;
		}
	}
	allocate_tickets(ans);
	return dp[n/2][n/2];
}
ll solve4(int n, int m, int k){
	vector<vector<int>>ans(n,vector<int>(m,-1));
	vector<pair<int,pair<int,int>>>process;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++) process.push_back({v[i][j],{i-1,j-1}});
	sort(process.begin(),process.end());
	int tot=n*m;
	ll resp=0;
	for(int i=0;i<(int)process.size();i++){
		pair<int,int>p=process[i].second;
		if(i>=tot/2){
			grande[p.first].push_back(p.second);
			resp+=process[i].first;
		}else{
			pequeno[p.first].push_back(p.second);
			resp-=process[i].first;
		}
	}
	for(int i=0;i<k;i++){
		vector<pair<int,int>>big;
		for(int j=0;j<n;j++) big.push_back({grande[j].size(),j});
		sort(big.begin(),big.end()); reverse(big.begin(),big.end());
		for(int j=0;j<n;j++){
			int id=big[j].second;
			if(j>=n/2){
				ans[id][pequeno[id].back()]=i;
				pequeno[id].pop_back();
			}else{
				ans[id][grande[id].back()]=i;
				grande[id].pop_back();
			}
		}
	}
	allocate_tickets(ans);
	return resp;
}
ll cost(int qtd, int id, int m, int k){
	int sum=0;
	for(int i=1;i<=qtd;i++) sum-=v[id][i];
	for(int i=m;i>m-k+qtd;i--) sum+=v[id][i];
	return sum;
}
bool in(int i){
	return 0<=i&&i<2*maxn*maxn;
}
ll find_maximum(int k, vector<vector<int>> x) {
	int n=x.size(), m=x[0].size();
	for(int i=1;i<=n;i++){
		me[i]=x[i-1][0];
		ma[i]=x[i-1][m-1];
		for(int j=1;j<=m;j++) v[i][j]=x[i-1][j-1];
	}
	if(k==1) return solve2(n,m);
	else if(k==m) return solve4(n,m,k);
	else{
		vector<vector<int>>ans(n,vector<int>(m,-1));
		for(int i=0;i<=n;i++)
			for(int j=0;j<2*maxn*maxn;j++) alt[i][j]=-inf;
		alt[0][maxn*maxn]=0;
		for(int i=1;i<=n;i++){ // brutando o id
			int sum=0;
			for(int j=m-1;j>=m-k;j--) sum+=x[i-1][j];
			//cout << "! ";
			for(int l=0;l<=k;l++){
				int diff=k-2*l;
				//cout << sum << " " << diff << "   ";
				for(int j=0;j<2*maxn*maxn;j++) if(in(j-diff)) alt[i][j]=max(alt[i][j],alt[i-1][j-diff]+sum);
				sum-=x[i-1][l]; // colocando o cara novo
				if(l<k) sum-=x[i-1][m-k+l]; // tirando o antigo
			}
			//cout << endl;
		}
		int agr=maxn*maxn, id=n, qm;
		while(id){
			//cerr << id << endl;
			qm=-1;
			for(int l=0;l<=k;l++){ // procurando qm era o melhor
				int diff=k-2*l;
				//cerr << alt[id][agr] << " " << alt[id-1][agr-diff] << " " << cost(l,id,m,k) << endl;
				if(agr-diff>=0&&agr-diff<2*maxn*maxn&&alt[id][agr]==alt[id-1][agr-diff]+cost(l,id,m,k)) qm=l;
			}
			//cout << qm << endl;
			assert(qm!=-1);
			for(int i=0;i<qm;i++) pequeno[id-1].push_back(i);
			for(int i=m-1;i>=m-k+qm;i--) grande[id-1].push_back(i);
			id--;
		}
		//cout << "wow" << endl;
		for(int i=0;i<k;i++){
			vector<pair<int,int>>big;
			for(int j=0;j<n;j++) big.push_back({grande[j].size(),j});
			sort(big.begin(),big.end()); reverse(big.begin(),big.end());
			for(int j=0;j<n;j++){
				int id=big[j].second;
				if(j>=n/2){
					ans[id][pequeno[id].back()]=i;
					pequeno[id].pop_back();
				}else{
					ans[id][grande[id].back()]=i;
					grande[id].pop_back();
				}
			}
		}
		allocate_tickets(ans);
		return alt[n][maxn*maxn];
	}
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 14 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10