Submission #419907

#	Time	Username	Problem	Language	Result	Execution time	Memory
419907		mosiashvililuka	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1022 ms	89520 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,f[1509][1509],k,pi,ee,qi,tes,t;
long long jm;
pair <int, int> q[3000009];
pair <int, pair <int, int> > p[3000009];
int bo[1509];
vector <vector <int> > ans;
/*void allocate_tickets(vector <vector <int> > XX){
	int qw=0,we=0;
	for(qw=0; qw<a; qw++){
		for(we=0; we<b; we++){
			cout<<XX[qw][we]<<" ";
		}
		cout<<endl;
	}
}*/
long long find_maximum(int K, vector<vector<int> > Xx) {
	k=K;
	a=Xx.size();b=Xx[0].size();
	ans.resize(a);
	for(i=0; i<a; i++){
		ans[i].resize(b);
		for(j=0; j<b; j++){
			f[i][j]=Xx[i][j];
		}
	}
	jm=0;
	for(i=0; i<a; i++){
		for(j=0; j<k; j++){
			jm-=f[i][j];
			bo[i]++;
			ii=i;jj=b-(k-j);
			pi++;
			p[pi].first=-(f[i][jj]+f[i][j]);
			p[pi].second=make_pair(i,jj);
		}
	}
	sort(p+1,p+pi+1);
	for(i=1; i<=pi; i++){
		p[i].first=-p[i].first;
	}
	ee=a*k/2;
	for(e=1; e<=ee; e++){
		i=p[e].second.first;j=p[e].second.second;
		jm+=p[e].first;
		ii=i;jj=b-(k-j);
		bo[i]--;
	}
	for(i=0; i<a; i++){
		for(j=0; j<b; j++){
			ans[i][j]=-1;
		}
	}
	t=0;
	while(k>0){
		qi=-1;
		for(i=0; i<a; i++){
			qi++;
			q[qi].first=bo[i];
			q[qi].second=i;
		}
		sort(q,q+qi+1);
		for(ii=0; ii<a/2; ii++){
			i=q[ii].second;
			j=b-(k-bo[i]);
			ans[i][j]=t;
		}
		for(ii=a/2; ii<a; ii++){
			i=q[ii].second;
			j=bo[i]-1;
			ans[i][j]=t;
			bo[i]--;
		}
		k--;t++;
	}
	allocate_tickets(ans);
	return jm;
}
/*int main(){
	vector <vector <int> > qw;
	cin>>a>>b>>k;
	qw.resize(a);
	for(i=0; i<a; i++){
		for(j=0; j<b; j++){
			cin>>c;
			qw[i].push_back(c);
		}
	}
	cout<<find_maximum(k,qw);
	return 0;
}*/

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