#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, int> PII;
#define ff first
#define ss second
long long find_maximum(int k1, vector <vector <int> > x) {
ll n = x.size();
ll m = x[0].size();
ll k = k1;
vector <vector <int> > answer(n, vector <int>(m, -1));
vector <vector <bool> > state(n, vector <bool>(m, 0));
// vector <vector <ll> > x(n, vector<ll>(m));
// for (int i = 0; i < n; i++)
// for (int j = 0; j < m; j++) x[i][j] = x1[i][j];
vector <ll> hiIdx(n+5, m-1);
vector <ll> loIdx(n+5, k-1);
// number picked : n * k -> + (n/2*k)(-), (n/2*k)(+)
set <PII> dif; // val, line
ll ans = 0, half = n * k / 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
state[i][j] = 1;
ans -= x[i][j];
}
dif.insert({-x[i][k-1]-x[i][m-1], i});
}
// cout << "here\n";
for (int i = 0; i < half; i++) { // n*m*log(n*m)
auto el = dif.begin();
dif.erase(el);
int a, b;
tie(a, b) = *el;
ans -= a;
state[b][loIdx[b]--] = 0;
state[b][hiIdx[b]--] = 1;
dif.insert({-x[b][loIdx[b]]-x[b][hiIdx[b]], b});
}
for (int i = 0; i < n; i++) {
int cur = 0;
for (int j = 0; j < m; j++) {
if (state[i][j]) answer[i][j] = cur++;
}
}
allocate_tickets(answer);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
272 KB |
Output is correct |
2 |
Correct |
0 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 |
3 ms |
844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
272 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 |
332 KB |
Output is correct |
5 |
Correct |
26 ms |
2284 KB |
Output is correct |
6 |
Runtime error |
333 ms |
55184 KB |
Execution killed with signal 11 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Contestant returned 2 but the tickets gives a total value of 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
224 KB |
Contestant returned 5 but the tickets gives a total value of 13 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Contestant returned 5 but the tickets gives a total value of 13 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Contestant returned 5 but the tickets gives a total value of 13 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
272 KB |
Output is correct |
2 |
Correct |
0 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 |
3 ms |
844 KB |
Output is correct |
7 |
Correct |
1 ms |
272 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
2 ms |
332 KB |
Output is correct |
11 |
Correct |
26 ms |
2284 KB |
Output is correct |
12 |
Runtime error |
333 ms |
55184 KB |
Execution killed with signal 11 |