Submission #432144

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
432144	2021-06-17T21:43:28 Z	peuch	Carnival Tickets (IOI20_tickets)	C++17	27 / 100	771 ms	105988 KB

tickets

#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;


long long find_maximum(int k, vector<vector<int> > x) {
	
	int n = x.size();
	int m = x[0].size();
	
	vector<vector<pair<long long, int> > > ord (n, vector<pair<long long, int> > (m));
	vector<deque<pair<int, int> > > pilha (n);
	vector<vector<int> > ans (n, vector<int> (m, -1));
	int maxi = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++)
			ord[i][j] = make_pair(x[i][j], j), maxi = max(maxi, x[i][j]);
		sort(ord[i].begin(), ord[i].end());
		for(int j = 0; j < m; j++)
			pilha[i].push_back(ord[i][j]);
	}
	
	if(maxi == 1){
		vector<int> coringa, zero, um;
		for(int i = 0; i < n; i++){
			coringa.push_back(i);
		}
		long long sum = 0;
		for(int i = 0; i < k; i++){
			int zeros = 0;
			int ones = 0;
			vector<int> marc(n, 0);
			for(int j = 0; j < n; j++){
				if(pilha[j].back().first == 0){
					ans[j][pilha[j].back().second] = i;
					pilha[j].pop_back();
					zeros++;
					marc[j] = 1;
				}
				if(pilha[j].front().first == 1){
					ans[j][pilha[j].front().second] = i;
					pilha[j].pop_front();
					ones++;
					marc[j] = 1;
				}
			}
			for(int j = 0; j < n; j++){
				if(marc[j]) continue;
				if(zeros < ones){
					ans[j][pilha[j].front().second] = i;
					pilha[j].pop_front();
					zeros++;
					marc[j] = 1;
				}
				else{
					ans[j][pilha[j].back().second] = i;
					pilha[j].pop_back();
					ones++;
					marc[j] = 1;
				}
			}
			sum += min(ones, zeros);
		}
		
		allocate_tickets(ans);
		return sum;
	}
	
	long long sum = 0;
	for(int c = 0; c < k; c++){
		vector<long long> dp (n);	
		vector<vector<bool> > bt (n, vector<bool> (n, 0));
		for(int i = 0; i < n; i++){
			for(int j = n / 2; j >= 0; j--){
				dp[j] = dp[j] - pilha[i].front().first;
				if(j != 0 && dp[j - 1] + pilha[i].back().first > dp[j]) dp[j] = dp[j - 1] + pilha[i].back().first, bt[i][j] = 1;
			}
		}
		
		int curI = n - 1, curJ = n / 2;
		while(curI >= 0){
			if(bt[curI][curJ]) curJ--, ans[curI][pilha[curI].back().second] = c, pilha[curI].pop_back();
			else ans[curI][pilha[curI].front().second] = c, pilha[curI].pop_front();
			curI--;
		}
		sum += dp[n / 2];
	}
	
	allocate_tickets(ans);
	return sum;	
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	5 ms	1996 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	3 ms	588 KB	Output is correct
5	Correct	37 ms	4528 KB	Output is correct
6	Correct	771 ms	105988 KB	Output is correct

Subtask #3

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	2 ms	588 KB	Output is correct
5	Correct	25 ms	4400 KB	Output is correct
6	Correct	726 ms	102548 KB	Output is correct
7	Correct	693 ms	98624 KB	Output is correct
8	Correct	4 ms	716 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Incorrect	1 ms	204 KB	Contestant returned 44 while correct return value is 45.
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	204 KB	Contestant returned 11 while correct return value is 13.
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	204 KB	Contestant returned 11 while correct return value is 13.
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	204 KB	Contestant returned 11 while correct return value is 13.
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	5 ms	1996 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	3 ms	588 KB	Output is correct
11	Correct	37 ms	4528 KB	Output is correct
12	Correct	771 ms	105988 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct
16	Correct	2 ms	588 KB	Output is correct
17	Correct	25 ms	4400 KB	Output is correct
18	Correct	726 ms	102548 KB	Output is correct
19	Correct	693 ms	98624 KB	Output is correct
20	Correct	4 ms	716 KB	Output is correct
21	Correct	1 ms	204 KB	Output is correct
22	Incorrect	1 ms	204 KB	Contestant returned 44 while correct return value is 45.
23	Halted	0 ms	0 KB	-