oj.uz

Submission #428364

# Submission time Handle Problem Language Result Execution time Memory
428364 2021-06-15T10:58:06 Z egekabas Carnival Tickets (IOI20_tickets) C++14
25 / 100
 695 ms 55480 KB 
#include "tickets.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size();
	int m = x[0].size();
	vector<int> beg(n), fin(n), sum(n);
	for(int i = 0; i < n; ++i){
		beg[i] = 0;
		fin[i] = m-1;
		for(int j = 0; j < m; ++j)
			sum[i] += x[i][j];
	}
	vector<vector<int>> ret(n, vector<int>(m, -1));
	ll ans = 0;
	for(int round = 0; round < k; ++round){
		vector<pii> vec;
		for(int i = 0; i < n; ++i)
			vec.pb({sum[i], i});
		sort(all(vec), greater<pii>());
		for(int i = 0; i < n; ++i){
			int idx = vec[i].ss;
			if(i < n/2){
				ans += x[idx][fin[idx]];
				ret[idx][fin[idx]] = round;
				sum[idx] -= x[idx][fin[idx]];
				--fin[idx];
			}
			else{
				ans -= x[idx][beg[idx]];
				ret[idx][beg[idx]] = round;
				sum[idx] -= x[idx][beg[idx]];
				++beg[idx];
			}
		}
	}
	allocate_tickets(ret);
	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 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Contestant returned 2444669794 while correct return value is 2727881086.
3 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 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 436 KB Output is correct
5 Correct 25 ms 2432 KB Output is correct
6 Correct 654 ms 54320 KB Output is correct
7 Correct 695 ms 54712 KB Output is correct
8 Correct 6 ms 460 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 7 ms 844 KB Output is correct
13 Correct 22 ms 2184 KB Output is correct
14 Correct 21 ms 2180 KB Output is correct
15 Correct 664 ms 55480 KB Output is correct

Subtask #4
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 Incorrect 1 ms 204 KB Contestant returned 24037843666 while correct return value is 24057831018.
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 2 ms 484 KB Contestant returned 38716776456 while correct return value is 39376297182.
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 2 ms 484 KB Contestant returned 38716776456 while correct return value is 39376297182.
3 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 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Incorrect 1 ms 204 KB Contestant returned 2444669794 while correct return value is 2727881086.
9 Halted 0 ms 0 KB -