Submission #738053

#	Time	Username	Problem	Language	Result	Execution time	Memory
738053		bobthebuilder	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	1 ms	212 KiB

tickets

#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define lowb(x) (x&(-x))
#define ALL(_x) _x.begin(),_x.end()
#define pii pair<int,int>
#define f first
#define s second
#define SORT_UNIQUE(x) sort(ALL(x)),x.erase(unique(ALL(x)),x.end())
#define ll long long
#define MNTO(x,y) x=min(x,y)
#define MXTO(x,y) x=max(x,y)
const ll INF64=4e18;
const int maxn=2e3+5;
ll cst[maxn];
int cnt[maxn];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<vector<ll>> dp(n+1,vector<ll>(k*n/2+1,-INF64));
	vector<vector<pii>> par(n+1,vector<pii>(k*n/2+1));
	vector<vector<int>> lbl(n,vector<int>(m,-1));
	vector<vector<pii>> arr;
	dp[0][0]=0;
	REP(i,n){
		vector<pii> z;
		REP(j,m){
			z.pb({x[i][j],j});
		}
		sort(ALL(z));
		arr.pb(z);
		cst[0]=0;
		REP(j,k) cst[0]-=z[j].f;
		REP1(j,k){
			cst[j]=cst[j-1]+z[k-j].f+z[m-j].f;
		}
		REP(a,k*n/2+1){
			if(dp[i][a]<0) continue;
			REP(j,k+1){
				if(a+j>k*n/2) break;
				MXTO(dp[i+1][a+j],dp[i][a]+cst[j]);
				if(dp[i+1][a+j]==dp[i][a]+cst[j]){
					par[i+1][a+j]={i,a};
				}
			}
		}
	}
	pii cur={n,k*n/2};
	while(cur.f){
		int pv=cur.s;
		cur=par[cur.f][cur.s];
		int pos=pv-cur.s,neg=0;
		REP(j,k){
			if(pos and cnt[j]!=n/2){
				cnt[j]++;
				lbl[cur.f][arr[cur.f][m-pos].s]=j;
				--pos;
			}
			else{
				lbl[cur.f][arr[cur.f][neg].s]=j;
				++neg;
			}
		}
	}
	allocate_tickets(lbl);
	return dp[n][k*n/2];
}

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