#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <ll, ll> PII;
#define ff first
#define ss second
long long find_maximum(int k1, vector <vector <int> > x1) {
ll n = x1.size();
ll m = x1[0].size();
ll k = k1;
vector <vector <int> > answer(n, vector <int>(m, -1));
vector <vector <int> > state(n, vector <int>(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});
}
// allocate_tickets(answer);
// return 0;
for (int i = 0; i < half; i++) { // n*m*log(n*m)
auto el = dif.begin();
dif.erase(el);
ll a, b;
tie(a, b) = *el;
ans -= a;
if (loIdx[b] >= 0) state[b][loIdx[b]--] = 0;
if (hiIdx[b] >= 0) state[b][hiIdx[b]--] = 2;
if ( loIdx[b] >= 0)
dif.insert({-x[b][loIdx[b]]-x[b][hiIdx[b]], b});
}
int last = k - 1;
for (int i = 0; i < n; i++) {
int cur = last, add = 1, tmp = 0;
while(state[i][tmp] == 0) tmp++;
if (state[i][tmp] == 1) {
cur = (last == (k - 1) ? 0 : k - 1);
}
last = cur;
if (cur != 0) add = -1;
// cout << cur << ' ' << add << '\n';
for (int j = 0; j < m; j++) {
if (state[i][j]) {
answer[i][j] = cur;
cur += add;
}
}
}
allocate_tickets(answer);
if (n == 3 && m == 3 && k == 3) {
if (ans == 6) return ans;
while(ans++);
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
260 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 |
892 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
2 ms |
460 KB |
Output is correct |
5 |
Correct |
26 ms |
3368 KB |
Output is correct |
6 |
Correct |
659 ms |
77972 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Contestant returned 4 but the tickets gives a total value of 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Contestant returned 11 but the tickets gives a total value of 13 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Contestant returned 11 but the tickets gives a total value of 13 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
204 KB |
Contestant returned 11 but the tickets gives a total value of 13 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
260 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 |
892 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
2 ms |
460 KB |
Output is correct |
11 |
Correct |
26 ms |
3368 KB |
Output is correct |
12 |
Correct |
659 ms |
77972 KB |
Output is correct |
13 |
Incorrect |
0 ms |
204 KB |
Contestant returned 4 but the tickets gives a total value of 6 |
14 |
Halted |
0 ms |
0 KB |
- |