Submission #1239518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239518		Sir_Ahmed_Imran	Carnival Tickets (IOI20_tickets)	C++17	0 / 100	165 ms	23684 KiB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 301
#define MAXM 9001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()

int cnt[MAXN][2];
ll a[MAXN][MAXN];
pll dp[MAXN][MAXM];
bool vis[MAXN][MAXN];

ll find_maximum(int k, vector<vector<int>> x) {
	int n, m, mx, o;
	n = x.size();
	m = x[0].size();
	mx = n * k / 2;
	for(int j = 0; j <= mx; j++)
		dp[0][j] = {-1e18, -1e18};
	dp[0][0] = {0, 0};
	for(int i = 0; i < n; i++){
		for(int j = 0; j < k; j++)
			a[i][0] -= x[i][j];
		for(int s = 0; s <= mx; s++)
			dp[i + 1][s] = {dp[i][s].ff + a[i][0], 0};
		for(ll j = 1; j <= k; j++){
			a[i][j] = a[i][j - 1] + x[i][k - j] + x[i][m - j];
			for(int s = 0; s <= mx - j; s++)
				dp[i + 1][s + j] = max(dp[i + 1][s + j], {dp[i][s].ff + a[i][j], j});
		}
	}
	ll ans = dp[n][mx].ff;
	vector<vector<int>> v = x;
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			v[i][j] = -1;
	for(int i = n - 1; i >= 0; i--){
		o = dp[i + 1][mx].ss;
		for(int s = 0; s < k - o; s++){
			for(int r = 0; r < k; r++){
				if(vis[r][i] || cnt[r][0] == n / 2)
					continue;
				vis[r][i] = 1;
				cnt[r][0]++;
				v[i][s] = r;
				break;
			}
		}
		for(int s = m - o; s < m; s++){
			for(int r = 0; r < k; r++){
				if(vis[r][i] || cnt[r][1] == n / 2)
					continue;
				vis[r][i] = 1;
				cnt[r][1]++;
				v[i][s] = r;
				break;
			}
		}
		mx -= o;
	}
	allocate_tickets(v);
	return ans;
}

• 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