답안 #823440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823440	2023-08-12T14:11:48 Z	NothingXD	카니발 티켓 (IOI20_tickets)	C++17	100 / 100	687 ms	80936 KB

tickets

#include "tickets.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1500 + 10;
const ll inf = 1e18;
int n, m, k, x[maxn][maxn], val[maxn];
ll a[maxn][maxn];
int ptl[maxn], ptr[maxn];

bool cmp(int x, int y){
	return val[x] > val[y];
}

ll find_maximum(int _k, vector<vector<int>> X) {
	n = X.size();
	m = X[0].size();
	k = _k;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			x[i][j] = X[i][j];
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < k; j++){
			a[i][0] -= x[i][j];
		}
		for (int j = 1; j <= k; j++){
			a[i][j] = a[i][j-1];
			a[i][j] += x[i][k-j];
			a[i][j] += x[i][m-j];
		}
	}
	ll res = 0;
	set<pll> st;
	for (int i = 0; i < n; i++){
		st.insert({a[i][1]-a[i][0], i});
		res += a[i][0];
	}
	for (int cnt = 1; cnt <= n*k/2; cnt++){
		auto it = st.end();
		it--;
		pii tmp = *it;
	//	debug(tmp.F, tmp.S);
		st.erase(it);
		res += tmp.F;
		val[tmp.S]++;
		if (val[tmp.S] < k) st.insert({a[tmp.S][val[tmp.S]+1]-a[tmp.S][val[tmp.S]], tmp.S});
	}
	//for (int i = 0; i < n; i++){
	//	debug(i, val[i]);
	//}
	vector<vector<int>> ans(n);
	for (int i = 0; i < n; i++){
		ptr[i] = m-1;
		ans[i].resize(m, -1);
	}
	for (int rnd = 0; rnd < k; rnd++){
		//debug(rnd);
		vector<int> idx;
		for (int i = 0; i < n; i++){
			idx.push_back(i);
		}
		sort(idx.begin(), idx.end(), cmp);
		for (int i = 0; i < n; i++){
			if (i < n/2){
				ans[idx[i]][ptr[idx[i]]] = rnd;
				val[idx[i]]--;
				ptr[idx[i]]--;
			}
			else{
				ans[idx[i]][ptl[idx[i]]] = rnd;
				ptl[idx[i]]++;
			}
		}
	}
	allocate_tickets(ans);
	return res;
}

Subtask #1

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	980 KB	Output is correct
5	Correct	2 ms	2772 KB	Output is correct
6	Correct	7 ms	12756 KB	Output is correct

Subtask #2

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	2 ms	1108 KB	Output is correct
5	Correct	19 ms	5184 KB	Output is correct
6	Correct	394 ms	66288 KB	Output is correct

Subtask #3

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	2 ms	1108 KB	Output is correct
5	Correct	18 ms	5460 KB	Output is correct
6	Correct	427 ms	76084 KB	Output is correct
7	Correct	462 ms	79484 KB	Output is correct
8	Correct	3 ms	1492 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	7 ms	2260 KB	Output is correct
13	Correct	16 ms	6748 KB	Output is correct
14	Correct	15 ms	3924 KB	Output is correct
15	Correct	462 ms	80032 KB	Output is correct

Subtask #4

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	3 ms	1108 KB	Output is correct
5	Correct	25 ms	5876 KB	Output is correct
6	Correct	5 ms	740 KB	Output is correct
7	Correct	11 ms	13140 KB	Output is correct
8	Correct	677 ms	80856 KB	Output is correct
9	Correct	604 ms	77144 KB	Output is correct
10	Correct	599 ms	75568 KB	Output is correct
11	Correct	651 ms	80936 KB	Output is correct

Subtask #5

12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	3 ms	1108 KB	Output is correct
3	Correct	2 ms	1108 KB	Output is correct
4	Correct	2 ms	1108 KB	Output is correct
5	Correct	2 ms	1108 KB	Output is correct
6	Correct	2 ms	1108 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	980 KB	Output is correct
9	Correct	2 ms	1108 KB	Output is correct
10	Correct	2 ms	1108 KB	Output is correct
11	Correct	2 ms	1108 KB	Output is correct
12	Correct	2 ms	1108 KB	Output is correct

Subtask #6

23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	3 ms	1108 KB	Output is correct
3	Correct	2 ms	1108 KB	Output is correct
4	Correct	2 ms	1108 KB	Output is correct
5	Correct	2 ms	1108 KB	Output is correct
6	Correct	2 ms	1108 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	980 KB	Output is correct
9	Correct	2 ms	1108 KB	Output is correct
10	Correct	2 ms	1108 KB	Output is correct
11	Correct	2 ms	1108 KB	Output is correct
12	Correct	2 ms	1108 KB	Output is correct
13	Correct	18 ms	5080 KB	Output is correct
14	Correct	17 ms	5144 KB	Output is correct
15	Correct	21 ms	5428 KB	Output is correct
16	Correct	31 ms	5836 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	3 ms	2900 KB	Output is correct
19	Correct	2 ms	2772 KB	Output is correct
20	Correct	20 ms	5588 KB	Output is correct
21	Correct	22 ms	5420 KB	Output is correct
22	Correct	23 ms	5748 KB	Output is correct
23	Correct	27 ms	5612 KB	Output is correct

Subtask #7

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	980 KB	Output is correct
5	Correct	2 ms	2772 KB	Output is correct
6	Correct	7 ms	12756 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	2 ms	1108 KB	Output is correct
11	Correct	19 ms	5184 KB	Output is correct
12	Correct	394 ms	66288 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	2 ms	1108 KB	Output is correct
17	Correct	18 ms	5460 KB	Output is correct
18	Correct	427 ms	76084 KB	Output is correct
19	Correct	462 ms	79484 KB	Output is correct
20	Correct	3 ms	1492 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	7 ms	2260 KB	Output is correct
25	Correct	16 ms	6748 KB	Output is correct
26	Correct	15 ms	3924 KB	Output is correct
27	Correct	462 ms	80032 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	0 ms	212 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	3 ms	1108 KB	Output is correct
32	Correct	25 ms	5876 KB	Output is correct
33	Correct	5 ms	740 KB	Output is correct
34	Correct	11 ms	13140 KB	Output is correct
35	Correct	677 ms	80856 KB	Output is correct
36	Correct	604 ms	77144 KB	Output is correct
37	Correct	599 ms	75568 KB	Output is correct
38	Correct	651 ms	80936 KB	Output is correct
39	Correct	0 ms	340 KB	Output is correct
40	Correct	3 ms	1108 KB	Output is correct
41	Correct	2 ms	1108 KB	Output is correct
42	Correct	2 ms	1108 KB	Output is correct
43	Correct	2 ms	1108 KB	Output is correct
44	Correct	2 ms	1108 KB	Output is correct
45	Correct	1 ms	340 KB	Output is correct
46	Correct	1 ms	980 KB	Output is correct
47	Correct	2 ms	1108 KB	Output is correct
48	Correct	2 ms	1108 KB	Output is correct
49	Correct	2 ms	1108 KB	Output is correct
50	Correct	2 ms	1108 KB	Output is correct
51	Correct	18 ms	5080 KB	Output is correct
52	Correct	17 ms	5144 KB	Output is correct
53	Correct	21 ms	5428 KB	Output is correct
54	Correct	31 ms	5836 KB	Output is correct
55	Correct	1 ms	340 KB	Output is correct
56	Correct	3 ms	2900 KB	Output is correct
57	Correct	2 ms	2772 KB	Output is correct
58	Correct	20 ms	5588 KB	Output is correct
59	Correct	22 ms	5420 KB	Output is correct
60	Correct	23 ms	5748 KB	Output is correct
61	Correct	27 ms	5612 KB	Output is correct
62	Correct	45 ms	11024 KB	Output is correct
63	Correct	46 ms	11008 KB	Output is correct
64	Correct	68 ms	13196 KB	Output is correct
65	Correct	229 ms	37416 KB	Output is correct
66	Correct	273 ms	41716 KB	Output is correct
67	Correct	11 ms	13140 KB	Output is correct
68	Correct	4 ms	840 KB	Output is correct
69	Correct	394 ms	66424 KB	Output is correct
70	Correct	512 ms	76112 KB	Output is correct
71	Correct	664 ms	80844 KB	Output is correct
72	Correct	519 ms	78792 KB	Output is correct
73	Correct	687 ms	77856 KB	Output is correct
74	Correct	452 ms	74944 KB	Output is correct
75	Correct	516 ms	74184 KB	Output is correct