oj.uz

Submission #428580

# Submission time Handle Problem Language Result Execution time Memory
428580 2021-06-15T12:59:56 Z alireza_kaviani Carnival Tickets (IOI20_tickets) C++17
39 / 100
 756 ms 65256 KB 
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;

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

#define sep		' '

const int MAXN = 1510;
int ptr[MAXN] , sum[MAXN] , L[MAXN] , R[MAXN] , F[MAXN][MAXN];

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size() , m = x[0].size();
	ll ans = 0;
	vector<pii> vec;
	vector<vector<int>> answer;
	for (int i = 0; i < n; i++) {
		vector<int> row(m , 0);
		sort(x[i].begin(), x[i].end());
		for (int j = 0; j < k; j++) {
			ans += x[i][m - k + j]; F[i][m - k + j] = 1;
			vec.push_back({x[i][j] + x[i][m - k + j] , i});
		}
		answer.push_back(row);
	}
	sort(vec.begin(), vec.end());
	for(int i = 0 ; i < n * k / 2 ; i++){
		int val = vec[i].first , id = vec[i].second;
		ans -= val;
		F[id][ptr[id]] = -1; F[id][m - k + ptr[id]] = 0;
		ptr[id]++;
	}
	for(int i = 0 ; i < n ; i++){
		L[i] = 0; R[i] = m - 1;
		for(int j = 0 ; j < m ; j++){
			sum[i] += F[i][j];
			answer[i][j] = -1;
		}
	}
	for(int i = 0 ; i < k ; i++){
		vector<pii> v;
		for(int j = 0 ; j < n ; j++){
			v.push_back({sum[j] , j});
		}
		sort(v.begin(), v.end());
		for(int j = 0 ; j < n ; j++){
			int id = v[j].second;
			if(j < n / 2){
				sum[id]++;
				answer[id][L[id]++] = i;
			}
			else{
				sum[id]--;
				answer[id][R[id]--] = i;
			}
		}
	}
	allocate_tickets(answer);
	return ans;
}

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 332 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 5 ms 6708 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 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 30 ms 3704 KB Output is correct
6 Correct 675 ms 57508 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 844 KB Output is correct
5 Correct 37 ms 4008 KB Output is correct
6 Correct 698 ms 62344 KB Output is correct
7 Correct 756 ms 65256 KB Output is correct
8 Incorrect 5 ms 972 KB Contestant returned 4979 but the tickets gives a total value of 4989
9 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Incorrect 1 ms 332 KB Contestant returned 23997938844 but the tickets gives a total value of 24057831018
4 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 3 ms 828 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 4 ms 844 KB Output is correct
10 Correct 3 ms 844 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 5 ms 880 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 716 KB Output is correct
3 Correct 3 ms 716 KB Output is correct
4 Correct 3 ms 828 KB Output is correct
5 Correct 4 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 4 ms 844 KB Output is correct
10 Correct 3 ms 844 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 5 ms 880 KB Output is correct
13 Correct 29 ms 3928 KB Output is correct
14 Correct 28 ms 3928 KB Output is correct
15 Correct 34 ms 4004 KB Output is correct
16 Incorrect 45 ms 4432 KB Contestant returned 22520901576614 but the tickets gives a total value of 22520953417030
17 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 332 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 1 ms 1612 KB Output is correct
6 Correct 5 ms 6708 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 3 ms 716 KB Output is correct
11 Correct 30 ms 3704 KB Output is correct
12 Correct 675 ms 57508 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 4 ms 844 KB Output is correct
17 Correct 37 ms 4008 KB Output is correct
18 Correct 698 ms 62344 KB Output is correct
19 Correct 756 ms 65256 KB Output is correct
20 Incorrect 5 ms 972 KB Contestant returned 4979 but the tickets gives a total value of 4989
21 Halted 0 ms 0 KB -