제출 #1239597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239597		Sir_Ahmed_Imran	카니발 티켓 (IOI20_tickets)	C++17	12 / 100	3094 ms	45632 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;
	vector<pair<int, pii>> u;
	vector<int> w[2];
	for(int i = n - 1; i >= 0; i--){
		o = dp[i + 1][mx].ss;
		for(int r = 0; r < k; r++){
			u.append({cnt[r][0], {r, 0}});
			u.append({cnt[r][1], {r, 1}});
		}
		for(int s = 0; s < k - o; s++)
			w[0].append(s);
		for(int s = m - o; s < m; s++)
			w[1].append(s);
		sort(all(u));
		for(auto & r : u){
			if(w[r.ss.ss].empty() || vis[r.ss.ff][i] == 1 || r.ff == n / 2 || v[i][w[r.ss.ss].back()] >= 0)
				continue;
			v[i][w[r.ss.ss].back()] = r.ss.ff;
			cnt[r.ss.ff][r.ss.ss]++;
			vis[r.ss.ff][i] = 1;
			w[r.ss.ss].pop_back();
		}
		u.clear(), w[0].clear(), w[1].clear();
		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: 12 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10