oj.uz

Submission #428574

# Submission time Handle Problem Language Result Execution time Memory
428574 2021-06-15T12:57:16 Z alireza_kaviani Carnival Tickets (IOI20_tickets) C++17
39 / 100
 727 ms 66252 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);
		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 332 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 1624 KB Output is correct
6 Correct 6 ms 6780 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 296 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 824 KB Output is correct
5 Correct 27 ms 4556 KB Output is correct
6 Correct 716 ms 60212 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 300 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 3 ms 832 KB Output is correct
5 Correct 27 ms 4164 KB Output is correct
6 Correct 716 ms 63264 KB Output is correct
7 Correct 727 ms 66252 KB Output is correct
8 Incorrect 4 ms 1100 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 204 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 844 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 4 ms 952 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 3 ms 828 KB Output is correct
11 Correct 4 ms 888 KB Output is correct
12 Correct 4 ms 844 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 844 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 4 ms 952 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 3 ms 828 KB Output is correct
11 Correct 4 ms 888 KB Output is correct
12 Correct 4 ms 844 KB Output is correct
13 Correct 27 ms 4676 KB Output is correct
14 Correct 30 ms 4836 KB Output is correct
15 Correct 33 ms 4808 KB Output is correct
16 Incorrect 40 ms 5256 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 332 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 1624 KB Output is correct
6 Correct 6 ms 6780 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 3 ms 824 KB Output is correct
11 Correct 27 ms 4556 KB Output is correct
12 Correct 716 ms 60212 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 300 KB Output is correct
16 Correct 3 ms 832 KB Output is correct
17 Correct 27 ms 4164 KB Output is correct
18 Correct 716 ms 63264 KB Output is correct
19 Correct 727 ms 66252 KB Output is correct
20 Incorrect 4 ms 1100 KB Contestant returned 4979 but the tickets gives a total value of 4989
21 Halted 0 ms 0 KB -