Submission #596284

#	Time	Username	Problem	Language	Result	Execution time	Memory
596284		Red_Inside	Carnival Tickets (IOI20_tickets)	C++17	39 / 100	3077 ms	2097152 KiB

tickets

#include "tickets.h"

#include <bits/stdc++.h>

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long

using namespace std;
const int maxn=1e6+10,LOG=17,mod=998244353;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define bt(i) (1 << (i))
//#define int ll
const ll inf=2e18;
#define y1 yy
#define prev pre
#define pii pair <int, int>

ll mni[maxn], mxi[maxn];
ll mx[maxn], mn[maxn];

bool cmp(pii a, pii b)
{
	return a.f > b.f;
}

long long find_maximum(int k, vector <vector <int> > a)
{
	vector <vector <int> > use;
	int n = a.size();
	int m = a[0].size();
	use = a;
	forn(0, i, n-1) forn(0, j, m-1) use[i][j] = -1;
	vector <vector <pii> > b;
	vector <vector <ll> > pref, suff, dp, pred;
	pref.assign(n + 2, {});
	suff.assign(n + 2, {});
	dp.assign(n + 2, {});
	pred.assign(n + 2, {});
	b.assign(n + 2, {});
	int SSS = k * n / 2;
	forn(0, i, n + 1)
	{
		pred[i].assign(SSS + 2, 0);
		dp[i].assign(SSS + 2, -inf);
		b[i].assign(m + 2, mp(0, 0));
		suff[i].assign(m + 2, 0);
		pref[i].assign(m + 2, 0);
	}
	forn(1, i, n)
	{
		forn(1, j, m)
		{
			b[i][j] = {a[i-1][j-1], j};
		}
		sort(b[i].begin() + 1, b[i].begin() + 1 + m);
		reverse(b[i].begin() + 1, b[i].begin() + 1 + m);
	}
	forn(1, i, n)
	{
		forn(1, j, m) pref[i][j] = pref[i][j - 1] + b[i][j].f;
		nfor(1, j, m) suff[i][j] = suff[i][j + 1] + b[i][j].f;
	}
	ll ret = 0;
	dp[0][0] = 0;
	forn(1, i, n)
	{
		int bor = min((i-1) * k, SSS);
		forn(0, j, bor)
		{
			forn(0, take, k)
			{
				if(take + j > SSS) break;
				if(dp[i][take+j] < dp[i-1][j] + pref[i][take] -suff[i][m-k+take+1])
				{
					pred[i][take+j] = take;
					dp[i][take+j]=dp[i-1][j]+pref[i][take]-suff[i][m-k+take+1];
				}
			}
		}
	}
	int cur = SSS;
	set <pii> st;
	forn(0, i, k-1)
	{
		st.insert({0, i});
	}
	ret = dp[n][SSS];
	nfor(1, i, n)
	{
		int take  = pred[i][cur];
		set <pii> nw;
		forn(1, j, take)
		{
			use[i-1][b[i][j].s-1] = st.begin()->s;
			pii temp = *st.begin();
			st.erase(st.begin());
			temp.f++;
			nw.insert(temp);
		}
		forn(m - k + take + 1, j, m)
		{
			use[i-1][b[i][j].s-1] = st.rbegin()->s;
			pii temp = *st.rbegin();
			temp.f--;
			st.erase(*st.rbegin());
			nw.insert(temp);
		}
		st = nw;
		cur -= take;
	}
	allocate_tickets(use);
	return ret;
}

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