oj.uz

Submission #432115

# Submission time Handle Problem Language Result Execution time Memory
432115 2021-06-17T21:12:07 Z peuch Carnival Tickets (IOI20_tickets) C++17
27 / 100
 3000 ms 105872 KB 
#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));
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++)
			ord[i][j] = make_pair(x[i][j], j);
		sort(ord[i].begin(), ord[i].end());
		for(int j = 0; j < m; j++)
			pilha[i].push_back(ord[i][j]);
	}
	
	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 7 ms 1996 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 628 KB Output is correct
5 Correct 29 ms 4528 KB Output is correct
6 Correct 729 ms 105872 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 3 ms 620 KB Output is correct
5 Correct 53 ms 4744 KB Output is correct
6 Correct 2633 ms 102744 KB Output is correct
7 Execution timed out 3054 ms 81824 KB Time limit exceeded
8 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 1 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 1 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 7 ms 1996 KB Output is correct
7 Correct 1 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 628 KB Output is correct
11 Correct 29 ms 4528 KB Output is correct
12 Correct 729 ms 105872 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 3 ms 620 KB Output is correct
17 Correct 53 ms 4744 KB Output is correct
18 Correct 2633 ms 102744 KB Output is correct
19 Execution timed out 3054 ms 81824 KB Time limit exceeded
20 Halted 0 ms 0 KB -