Submission #738072

#	Time	Username	Problem	Language	Result	Execution time	Memory
738072		bobthebuilder	Carnival Tickets (IOI20_tickets)	C++17	62 / 100	1231 ms	2097152 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;
int cnt[maxn];
bool vis[maxn];
int tot[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));
	dp[0][0]=0;
	vector<pii> cst;
	ll ans=0;
	REP(i,n){
		REP(j,k) ans-=x[i][j];
		REP1(j,k){
			cst.pb({x[i][k-j]+x[i][m-j],i});
		}
	}
	sort(ALL(cst));
	reverse(ALL(cst));
	REP(j,k*n/2){
		ans+=cst[j].f;
		tot[cst[j].s]++;
	}
	int pp=0;
	REP(i,n){
		int pos=tot[i],neg=0;
		REP(j,pos){
			lbl[i][m-j-1]=pp;
			vis[pp]=1;
			++pp;
			pp%=k;
		}
		REP(j,k){
			if(!vis[j]){
				lbl[i][neg]=j;
				++neg;
			}
			vis[j]=0;
		}
	}
	allocate_tickets(lbl);
	return ans;
}

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