#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int) (x).size())
const int MAXN = 1513;
const long long LLINF = 3e18;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, M, K;
ll grid[MAXN][MAXN];
ll smallest[MAXN][MAXN];
// vl dp[MAXN];//at row i, we have j -s. what's the best we could get?
// vi parent[MAXN];
vpl pq;
vl nums[MAXN];
int mm[MAXN], pp[MAXN];
int mtake[MAXN], ptake[MAXN];
bitset<MAXN> rec;
ll res;
vector<vi> ans;
long long find_maximum(int k, vector<vi> xx)
{
K = k; N = SZ(xx); M = SZ(xx[0]);
ans.resize(N);
FOR(i, 0, N)
{
ans[i].resize(M);
FOR(j, 0, M)
{
ans[i][j] = -1;
grid[i][j] = xx[i][j];
}
FOR(j, 0, M)
{
smallest[i][j + 1] = smallest[i][j] + grid[i][j];
}
}
// dp[0].PB(0);
// FOR(i, 0, N)
// {
// //you're choosing K numbers.
// dp[i + 1].resize(K * (i + 1) + 1);
// parent[i + 1].resize(K * (i + 1) + 1);
// fill(ALL(dp[i + 1]), -LLINF);
// FOR(j, 0, K * i + 1)
// {
// FOR(k, 0, K + 1) //choose k -s
// {
// ll cand = dp[i][j] - smallest[i][k] + biggest[i][K - k];
// if (cand > dp[i + 1][j + k])
// {
// dp[i + 1][j + k] = cand;
// parent[i + 1][j + k] = k;
// // cerr << "PARENT " << i + 1 << ' ' << j + k << " = " << parent[i + 1][j + k] << endl;
// }
// }
// }
// }
FOR(i, 0, N)
{
FOR(j, 0, K)
{
pq.PB({grid[i][M - 1 - j] + grid[i][K - 1 - j], i});
}
res -= smallest[i][K];
mtake[i] = K;
ptake[i] = 0;
}
// cerr << "RES = " << res << endl;
sort(ALL(pq), greater<pll>());
FOR(i, 0, K * (N / 2))
{
int idx = pq[i].se;
mtake[idx]--;
ptake[idx]++;
res += pq[i].fi;
}
// k = K * (N / 2);
// FORD(i, N + 1, 1)
// {
// // cerr << "parent " << i << ' ' << k << " = " << parent[i][k] << endl;
// mtake[i - 1] = parent[i][k];
// k -= parent[i][k];
// }
FOR(i, 0, N)
{
ptake[i] = K - mtake[i];
mm[i] = 0;
pp[i] = M - 1;
// cerr << pp[i] << ' ' << M - 1 - ptake[i] << endl;
// cerr << "ptake " << i << " = " << ptake[i] << endl;
}
FOR(i, 0, K)
{
// cerr << "work " << i << endl;
int minuses = 0, pluses = 0;
FOR(j, 0, N)
{
rec[j] = false;
if (mm[j] == mtake[j])
{
//you have to make it a plus
// cerr << "make " << j << " plus\n";
pluses++;
ans[j][pp[j]] = i;
pp[j]--;
rec[j] = true;
}
else if (pp[j] == M - 1 - ptake[j])
{
// cerr << "make " << j << " mnus\n";
minuses++;
ans[j][mm[j]] = i;
mm[j]++;
rec[j] = true;
}
}
FOR(j, 0, N)
{
if (rec[j]) continue;
if (pluses < N / 2)
{
// cerr << "make " << j << " PLus\n";
pluses++;
ans[j][pp[j]] = i;
pp[j]--;
rec[j] = true;
}
else
{
// cerr << "make " << j << " MNus\n";
minuses++;
ans[j][mm[j]] = i;
mm[j]++;
rec[j] = true;
}
}
//for each row that already got all -s and all +s factor it in.
}
//as long as we make sure to choose enough +s and enough -s we shouldn't need to worry right.
//keep a set of (value, position.)
//i think you always want to take x[0] or x[end] right?
//so if x is 1, then
allocate_tickets(ans);
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
972 KB |
Output is correct |
5 |
Correct |
2 ms |
2764 KB |
Output is correct |
6 |
Correct |
8 ms |
12748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
1228 KB |
Output is correct |
5 |
Correct |
27 ms |
6204 KB |
Output is correct |
6 |
Correct |
621 ms |
87108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
3 ms |
1228 KB |
Output is correct |
5 |
Correct |
28 ms |
6980 KB |
Output is correct |
6 |
Correct |
623 ms |
105556 KB |
Output is correct |
7 |
Correct |
644 ms |
116200 KB |
Output is correct |
8 |
Correct |
4 ms |
1744 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
8 ms |
2632 KB |
Output is correct |
13 |
Correct |
24 ms |
8172 KB |
Output is correct |
14 |
Correct |
23 ms |
5536 KB |
Output is correct |
15 |
Correct |
661 ms |
121420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
4 ms |
1356 KB |
Output is correct |
5 |
Correct |
38 ms |
7680 KB |
Output is correct |
6 |
Correct |
6 ms |
1276 KB |
Output is correct |
7 |
Correct |
14 ms |
13452 KB |
Output is correct |
8 |
Correct |
934 ms |
130860 KB |
Output is correct |
9 |
Correct |
875 ms |
129096 KB |
Output is correct |
10 |
Correct |
864 ms |
126676 KB |
Output is correct |
11 |
Correct |
924 ms |
130924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
1228 KB |
Output is correct |
3 |
Correct |
3 ms |
1228 KB |
Output is correct |
4 |
Correct |
3 ms |
1228 KB |
Output is correct |
5 |
Correct |
3 ms |
1228 KB |
Output is correct |
6 |
Correct |
4 ms |
1356 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
972 KB |
Output is correct |
9 |
Correct |
3 ms |
1228 KB |
Output is correct |
10 |
Correct |
3 ms |
1228 KB |
Output is correct |
11 |
Correct |
3 ms |
1356 KB |
Output is correct |
12 |
Correct |
3 ms |
1356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
3 ms |
1228 KB |
Output is correct |
3 |
Correct |
3 ms |
1228 KB |
Output is correct |
4 |
Correct |
3 ms |
1228 KB |
Output is correct |
5 |
Correct |
3 ms |
1228 KB |
Output is correct |
6 |
Correct |
4 ms |
1356 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
972 KB |
Output is correct |
9 |
Correct |
3 ms |
1228 KB |
Output is correct |
10 |
Correct |
3 ms |
1228 KB |
Output is correct |
11 |
Correct |
3 ms |
1356 KB |
Output is correct |
12 |
Correct |
3 ms |
1356 KB |
Output is correct |
13 |
Correct |
27 ms |
6156 KB |
Output is correct |
14 |
Correct |
28 ms |
6236 KB |
Output is correct |
15 |
Correct |
32 ms |
6840 KB |
Output is correct |
16 |
Correct |
38 ms |
7732 KB |
Output is correct |
17 |
Correct |
2 ms |
460 KB |
Output is correct |
18 |
Correct |
4 ms |
3176 KB |
Output is correct |
19 |
Correct |
3 ms |
2940 KB |
Output is correct |
20 |
Correct |
31 ms |
7308 KB |
Output is correct |
21 |
Correct |
33 ms |
7776 KB |
Output is correct |
22 |
Correct |
35 ms |
7736 KB |
Output is correct |
23 |
Correct |
36 ms |
8212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
972 KB |
Output is correct |
5 |
Correct |
2 ms |
2764 KB |
Output is correct |
6 |
Correct |
8 ms |
12748 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
3 ms |
1228 KB |
Output is correct |
11 |
Correct |
27 ms |
6204 KB |
Output is correct |
12 |
Correct |
621 ms |
87108 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
3 ms |
1228 KB |
Output is correct |
17 |
Correct |
28 ms |
6980 KB |
Output is correct |
18 |
Correct |
623 ms |
105556 KB |
Output is correct |
19 |
Correct |
644 ms |
116200 KB |
Output is correct |
20 |
Correct |
4 ms |
1744 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
8 ms |
2632 KB |
Output is correct |
25 |
Correct |
24 ms |
8172 KB |
Output is correct |
26 |
Correct |
23 ms |
5536 KB |
Output is correct |
27 |
Correct |
661 ms |
121420 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
4 ms |
1356 KB |
Output is correct |
32 |
Correct |
38 ms |
7680 KB |
Output is correct |
33 |
Correct |
6 ms |
1276 KB |
Output is correct |
34 |
Correct |
14 ms |
13452 KB |
Output is correct |
35 |
Correct |
934 ms |
130860 KB |
Output is correct |
36 |
Correct |
875 ms |
129096 KB |
Output is correct |
37 |
Correct |
864 ms |
126676 KB |
Output is correct |
38 |
Correct |
924 ms |
130924 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
3 ms |
1228 KB |
Output is correct |
41 |
Correct |
3 ms |
1228 KB |
Output is correct |
42 |
Correct |
3 ms |
1228 KB |
Output is correct |
43 |
Correct |
3 ms |
1228 KB |
Output is correct |
44 |
Correct |
4 ms |
1356 KB |
Output is correct |
45 |
Correct |
1 ms |
460 KB |
Output is correct |
46 |
Correct |
1 ms |
972 KB |
Output is correct |
47 |
Correct |
3 ms |
1228 KB |
Output is correct |
48 |
Correct |
3 ms |
1228 KB |
Output is correct |
49 |
Correct |
3 ms |
1356 KB |
Output is correct |
50 |
Correct |
3 ms |
1356 KB |
Output is correct |
51 |
Correct |
27 ms |
6156 KB |
Output is correct |
52 |
Correct |
28 ms |
6236 KB |
Output is correct |
53 |
Correct |
32 ms |
6840 KB |
Output is correct |
54 |
Correct |
38 ms |
7732 KB |
Output is correct |
55 |
Correct |
2 ms |
460 KB |
Output is correct |
56 |
Correct |
4 ms |
3176 KB |
Output is correct |
57 |
Correct |
3 ms |
2940 KB |
Output is correct |
58 |
Correct |
31 ms |
7308 KB |
Output is correct |
59 |
Correct |
33 ms |
7776 KB |
Output is correct |
60 |
Correct |
35 ms |
7736 KB |
Output is correct |
61 |
Correct |
36 ms |
8212 KB |
Output is correct |
62 |
Correct |
73 ms |
16400 KB |
Output is correct |
63 |
Correct |
74 ms |
16456 KB |
Output is correct |
64 |
Correct |
101 ms |
20532 KB |
Output is correct |
65 |
Correct |
347 ms |
64608 KB |
Output is correct |
66 |
Correct |
405 ms |
73028 KB |
Output is correct |
67 |
Correct |
13 ms |
13524 KB |
Output is correct |
68 |
Correct |
6 ms |
1352 KB |
Output is correct |
69 |
Correct |
635 ms |
89772 KB |
Output is correct |
70 |
Correct |
775 ms |
108140 KB |
Output is correct |
71 |
Correct |
938 ms |
145932 KB |
Output is correct |
72 |
Correct |
830 ms |
133504 KB |
Output is correct |
73 |
Correct |
867 ms |
137620 KB |
Output is correct |
74 |
Correct |
696 ms |
113508 KB |
Output is correct |
75 |
Correct |
750 ms |
112868 KB |
Output is correct |