oj.uz

Submission #744741

# Submission time Handle Problem Language Result Execution time Memory
744741 2023-05-19T04:40:34 Z josanneo22 Carnival Tickets (IOI20_tickets) C++17
0 / 100
 31 ms 3652 KB 
#include <bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
using namespace std;

#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second 
#include "tickets.h"
#include <vector>

long long find_maximum(int k, vector<vector<int>> x) {
	int n = x.size(), m = x[0].size();
	long long ans = 0;
	vector<pii> todo;
	for(int i=0;i<n;i++){
		for(int j=m-k;j<m;j++) ans += x[i][j];
		for(int j=0;j<k;j++) todo.pb({ -x[i][j] - x[i][m - k + j],i });
	}
	sort(todo.rbegin(),todo.rend());
	vector<int> num(n);
	for(int i=0;i<n*k/2;i++){
		num[todo[i].se]++;
		ans += todo[i].fi;
	}
	vector<vector<int>> ret(n, vector<int>(m, -1));
	vector<int> lo(n, 0), hi(n, m - 1);
	for(int i=0;i<k;i++) {
		vector<int> ha;
		int x = 0;
		for(int j=0;j<k;j++) {
			if (num[j] == k - i) {
				ret[j][lo[j]++] = i;
				num[j]--;
				x++;
			}
			else if (num[j] == 0) {
				ret[j][hi[j]--] = i;
			}
			else {
				ha.pb(j);
			}
		}
		for(auto&t:ha) {
			if (x < n / 2) {
				ret[t][lo[t]++] = i;
				num[t] --;
				x++;
			}
			else {
				ret[t][hi[t]--] = i;
			}
		}
		assert(x == n / 2);
	}
	allocate_tickets(ret);
	return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB There is no ticket of color 1 on day 0
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 KB There is no ticket of color 1 on day 0
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 31 ms 3652 KB Output is correct
6 Runtime error 4 ms 1232 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Runtime error 2 ms 596 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Runtime error 2 ms 596 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB There is no ticket of color 1 on day 0
2 Halted 0 ms 0 KB -