Submission #428545

#	Time	Username	Problem	Language	Result	Execution time	Memory
428545		alishahali1382	Carnival Tickets (IOI20_tickets)	C++14	100 / 100	1235 ms	401788 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": "; for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())

const int inf=1000000100; // 1e9
const ll INF=10000000001000000; // 1e16
const int mod=1000000007;
const int MAXN=1510, LOG=20;

int n, m, k, x, y, u, v, t, a, b, ans;
int A[MAXN][MAXN], Ted[MAXN];
ll B[MAXN][MAXN];
vector<vi> out;
vi out1[MAXN], out2[MAXN];

vector<ll> dp[MAXN<<2];
vi par[MAXN<<2];

inline bool upd(ll &x, ll y){
	if (x>=y) return 0;
	x=y;
	return 1;
}
void divide(int id, int tl, int tr){
	dp[id].resize((tr-tl)*k+1);
	par[id].resize((tr-tl)*k+1);
	if (tr-tl==1){
		for (int i=0; i<=k; i++) dp[id][i]=B[tl][i];
		return ;
	}
	int mid=(tl+tr)>>1;
	divide(id<<1, tl, mid);
	divide(id<<1 | 1, mid, tr);
	par[id][0]=0;
	dp[id][0]=dp[id<<1][0]+dp[id<<1 | 1][0];
	int x=0, y=0;
	for (int i=1; i<SZ(dp[id]); i++){
		if (x==SZ(dp[id<<1])-1) y++;
		else if (y==SZ(dp[id<<1 | 1])-1) x++;
		else{
			ll valx=dp[id<<1][x+1]-dp[id<<1][x];
			ll valy=dp[id<<1 | 1][y+1]-dp[id<<1 | 1][y];
			if (valx>valy) x++;
			else y++;
		}
		dp[id][i]=dp[id<<1][x]+dp[id<<1 | 1][y];
		par[id][i]=x;
	}
	/*
	cerr<<"\n";
	debug2(tl, tr)
	for (int i=0; i<SZ(dp[id]); i++) cerr<<dp[id][i]<<" ";
	cerr<<"\n";
	cerr<<"\n";*/

}
void Build(int id, int tl, int tr, int ted){
	if (tr-tl==1){
		Ted[tl]=ted;
		return ;
	}
	int mid=(tl+tr)>>1;
	Build(id<<1, tl, mid, par[id][ted]);
	Build(id<<1 | 1, mid, tr, ted-par[id][ted]);
}

ll find_maximum(int _k, vector<vi> _A) {
	n=SZ(_A);
	m=SZ(_A[0]);
	k=_k;
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++) A[i][j]=_A[i-1][j-1];
		for (int j=1; j<=k; j++) B[i][0]-=A[i][j];
		for (int j=1; j<=k; j++) B[i][j]=B[i][j-1]+A[i][m-j+1]+A[i][k-j+1];
		// B convex increasing
		// B[j]<=B[j+1]
		// B[j]-B[j-1]>=B[j+1]-B[j]
		// debug2(B[i][0], B[i][1])
	}
	out.resize(n, vector<int>(m, -1));

	divide(1, 1, n+1);
	ll res=dp[1][n*k/2];
	Build(1, 1, n+1, n*k/2);

	for (int i=1; i<=n; i++){
		for (int x=1; x<=k-Ted[i]; x++) out1[i].pb(x);
		for (int x=0; x<Ted[i]; x++) out2[i].pb(m-x);
	}
	while (k--){
		vector<pii> vec;
		for (int i=1; i<=n; i++) vec.pb({SZ(out1[i]), i});
		sort(all(vec));
		for (int ii=1; ii<=n; ii++){
			int i=vec[ii-1].second;
			if (ii>n/2){
				assert(SZ(out1[i]));
				out[i-1][out1[i].back()-1]=k;
				out1[i].pop_back();
			}
			else{
				assert(SZ(out2[i]));
				out[i-1][out2[i].back()-1]=k;
				out2[i].pop_back();
			}
		}
	}
	allocate_tickets(out);
	return res;
}

• 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