#include "tickets.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": "; for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())
const int inf=1000000100; // 1e9
const ll INF=10000000001000000; // 1e16
const int mod=1000000007;
const int MAXN=1510, LOG=20;
int n, m, k, x, y, u, v, t, a, b, ans;
int A[MAXN][MAXN], Ted[MAXN];
ll B[MAXN][MAXN];
vector<vi> out;
vi out1[MAXN], out2[MAXN];
vector<ll> dp[MAXN<<2];
vi par[MAXN<<2];
inline bool upd(ll &x, ll y){
if (x>=y) return 0;
x=y;
return 1;
}
void divide(int id, int tl, int tr){
dp[id].resize((tr-tl)*k+1);
par[id].resize((tr-tl)*k+1);
if (tr-tl==1){
for (int i=0; i<=k; i++) dp[id][i]=B[tl][i];
return ;
}
int mid=(tl+tr)>>1;
divide(id<<1, tl, mid);
divide(id<<1 | 1, mid, tr);
par[id][0]=0;
dp[id][0]=dp[id<<1][0]+dp[id<<1 | 1][0];
int x=0, y=0;
for (int i=1; i<SZ(dp[id]); i++){
if (x==SZ(dp[id<<1])-1) y++;
else if (y==SZ(dp[id<<1 | 1])-1) x++;
else{
ll valx=dp[id<<1][x+1]-dp[id<<1][x];
ll valy=dp[id<<1 | 1][y+1]-dp[id<<1 | 1][y];
if (valx>valy) x++;
else y++;
}
dp[id][i]=dp[id<<1][x]+dp[id<<1 | 1][y];
par[id][i]=x;
}
/*
cerr<<"\n";
debug2(tl, tr)
for (int i=0; i<SZ(dp[id]); i++) cerr<<dp[id][i]<<" ";
cerr<<"\n";
cerr<<"\n";*/
}
void Build(int id, int tl, int tr, int ted){
if (tr-tl==1){
Ted[tl]=ted;
return ;
}
int mid=(tl+tr)>>1;
Build(id<<1, tl, mid, par[id][ted]);
Build(id<<1 | 1, mid, tr, ted-par[id][ted]);
}
ll find_maximum(int _k, vector<vi> _A) {
n=SZ(_A);
m=SZ(_A[0]);
k=_k;
for (int i=1; i<=n; i++){
for (int j=1; j<=m; j++) A[i][j]=_A[i-1][j-1];
for (int j=1; j<=k; j++) B[i][0]-=A[i][j];
for (int j=1; j<=k; j++) B[i][j]=B[i][j-1]+A[i][m-j+1]+A[i][k-j+1];
// B convex increasing
// B[j]<=B[j+1]
// B[j]-B[j-1]>=B[j+1]-B[j]
// debug2(B[i][0], B[i][1])
}
out.resize(n, vector<int>(m, -1));
divide(1, 1, n+1);
ll res=dp[1][n*k/2];
Build(1, 1, n+1, n*k/2);
for (int i=1; i<=n; i++){
for (int x=1; x<=k-Ted[i]; x++) out1[i].pb(x);
for (int x=0; x<Ted[i]; x++) out2[i].pb(m-x);
}
while (k--){
vector<pii> vec;
for (int i=1; i<=n; i++) vec.pb({SZ(out1[i]), i});
sort(all(vec));
for (int ii=1; ii<=n; ii++){
int i=vec[ii-1].second;
if (ii>n/2){
assert(SZ(out1[i]));
out[i-1][out1[i].back()-1]=k;
out1[i].pop_back();
}
else{
assert(SZ(out2[i]));
out[i-1][out2[i].back()-1]=k;
out2[i].pop_back();
}
}
}
allocate_tickets(out);
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
716 KB |
Output is correct |
3 |
Correct |
1 ms |
716 KB |
Output is correct |
4 |
Correct |
1 ms |
1228 KB |
Output is correct |
5 |
Correct |
2 ms |
3148 KB |
Output is correct |
6 |
Correct |
9 ms |
13388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
716 KB |
Output is correct |
4 |
Correct |
3 ms |
1484 KB |
Output is correct |
5 |
Correct |
28 ms |
5444 KB |
Output is correct |
6 |
Correct |
606 ms |
66916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
716 KB |
Output is correct |
4 |
Correct |
3 ms |
1740 KB |
Output is correct |
5 |
Correct |
33 ms |
11076 KB |
Output is correct |
6 |
Correct |
821 ms |
236660 KB |
Output is correct |
7 |
Correct |
900 ms |
293840 KB |
Output is correct |
8 |
Correct |
5 ms |
2764 KB |
Output is correct |
9 |
Correct |
1 ms |
716 KB |
Output is correct |
10 |
Correct |
1 ms |
716 KB |
Output is correct |
11 |
Correct |
1 ms |
716 KB |
Output is correct |
12 |
Correct |
13 ms |
4084 KB |
Output is correct |
13 |
Correct |
32 ms |
13248 KB |
Output is correct |
14 |
Correct |
29 ms |
10616 KB |
Output is correct |
15 |
Correct |
967 ms |
336992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
588 KB |
Output is correct |
3 |
Correct |
1 ms |
716 KB |
Output is correct |
4 |
Correct |
4 ms |
2124 KB |
Output is correct |
5 |
Correct |
44 ms |
16704 KB |
Output is correct |
6 |
Correct |
7 ms |
1996 KB |
Output is correct |
7 |
Correct |
17 ms |
15692 KB |
Output is correct |
8 |
Correct |
1179 ms |
401648 KB |
Output is correct |
9 |
Correct |
1134 ms |
376972 KB |
Output is correct |
10 |
Correct |
1139 ms |
372476 KB |
Output is correct |
11 |
Correct |
1235 ms |
401788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
3 ms |
1484 KB |
Output is correct |
3 |
Correct |
3 ms |
1484 KB |
Output is correct |
4 |
Correct |
3 ms |
1612 KB |
Output is correct |
5 |
Correct |
3 ms |
1740 KB |
Output is correct |
6 |
Correct |
4 ms |
1868 KB |
Output is correct |
7 |
Correct |
1 ms |
716 KB |
Output is correct |
8 |
Correct |
1 ms |
1356 KB |
Output is correct |
9 |
Correct |
4 ms |
1868 KB |
Output is correct |
10 |
Correct |
4 ms |
1868 KB |
Output is correct |
11 |
Correct |
4 ms |
1996 KB |
Output is correct |
12 |
Correct |
4 ms |
1996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
3 ms |
1484 KB |
Output is correct |
3 |
Correct |
3 ms |
1484 KB |
Output is correct |
4 |
Correct |
3 ms |
1612 KB |
Output is correct |
5 |
Correct |
3 ms |
1740 KB |
Output is correct |
6 |
Correct |
4 ms |
1868 KB |
Output is correct |
7 |
Correct |
1 ms |
716 KB |
Output is correct |
8 |
Correct |
1 ms |
1356 KB |
Output is correct |
9 |
Correct |
4 ms |
1868 KB |
Output is correct |
10 |
Correct |
4 ms |
1868 KB |
Output is correct |
11 |
Correct |
4 ms |
1996 KB |
Output is correct |
12 |
Correct |
4 ms |
1996 KB |
Output is correct |
13 |
Correct |
29 ms |
5476 KB |
Output is correct |
14 |
Correct |
28 ms |
5860 KB |
Output is correct |
15 |
Correct |
37 ms |
11076 KB |
Output is correct |
16 |
Correct |
45 ms |
16616 KB |
Output is correct |
17 |
Correct |
1 ms |
716 KB |
Output is correct |
18 |
Correct |
5 ms |
3532 KB |
Output is correct |
19 |
Correct |
4 ms |
3276 KB |
Output is correct |
20 |
Correct |
38 ms |
12740 KB |
Output is correct |
21 |
Correct |
38 ms |
12424 KB |
Output is correct |
22 |
Correct |
42 ms |
15824 KB |
Output is correct |
23 |
Correct |
42 ms |
15300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
588 KB |
Output is correct |
2 |
Correct |
1 ms |
716 KB |
Output is correct |
3 |
Correct |
1 ms |
716 KB |
Output is correct |
4 |
Correct |
1 ms |
1228 KB |
Output is correct |
5 |
Correct |
2 ms |
3148 KB |
Output is correct |
6 |
Correct |
9 ms |
13388 KB |
Output is correct |
7 |
Correct |
1 ms |
588 KB |
Output is correct |
8 |
Correct |
1 ms |
588 KB |
Output is correct |
9 |
Correct |
1 ms |
716 KB |
Output is correct |
10 |
Correct |
3 ms |
1484 KB |
Output is correct |
11 |
Correct |
28 ms |
5444 KB |
Output is correct |
12 |
Correct |
606 ms |
66916 KB |
Output is correct |
13 |
Correct |
1 ms |
588 KB |
Output is correct |
14 |
Correct |
1 ms |
588 KB |
Output is correct |
15 |
Correct |
1 ms |
716 KB |
Output is correct |
16 |
Correct |
3 ms |
1740 KB |
Output is correct |
17 |
Correct |
33 ms |
11076 KB |
Output is correct |
18 |
Correct |
821 ms |
236660 KB |
Output is correct |
19 |
Correct |
900 ms |
293840 KB |
Output is correct |
20 |
Correct |
5 ms |
2764 KB |
Output is correct |
21 |
Correct |
1 ms |
716 KB |
Output is correct |
22 |
Correct |
1 ms |
716 KB |
Output is correct |
23 |
Correct |
1 ms |
716 KB |
Output is correct |
24 |
Correct |
13 ms |
4084 KB |
Output is correct |
25 |
Correct |
32 ms |
13248 KB |
Output is correct |
26 |
Correct |
29 ms |
10616 KB |
Output is correct |
27 |
Correct |
967 ms |
336992 KB |
Output is correct |
28 |
Correct |
1 ms |
588 KB |
Output is correct |
29 |
Correct |
1 ms |
588 KB |
Output is correct |
30 |
Correct |
1 ms |
716 KB |
Output is correct |
31 |
Correct |
4 ms |
2124 KB |
Output is correct |
32 |
Correct |
44 ms |
16704 KB |
Output is correct |
33 |
Correct |
7 ms |
1996 KB |
Output is correct |
34 |
Correct |
17 ms |
15692 KB |
Output is correct |
35 |
Correct |
1179 ms |
401648 KB |
Output is correct |
36 |
Correct |
1134 ms |
376972 KB |
Output is correct |
37 |
Correct |
1139 ms |
372476 KB |
Output is correct |
38 |
Correct |
1235 ms |
401788 KB |
Output is correct |
39 |
Correct |
1 ms |
588 KB |
Output is correct |
40 |
Correct |
3 ms |
1484 KB |
Output is correct |
41 |
Correct |
3 ms |
1484 KB |
Output is correct |
42 |
Correct |
3 ms |
1612 KB |
Output is correct |
43 |
Correct |
3 ms |
1740 KB |
Output is correct |
44 |
Correct |
4 ms |
1868 KB |
Output is correct |
45 |
Correct |
1 ms |
716 KB |
Output is correct |
46 |
Correct |
1 ms |
1356 KB |
Output is correct |
47 |
Correct |
4 ms |
1868 KB |
Output is correct |
48 |
Correct |
4 ms |
1868 KB |
Output is correct |
49 |
Correct |
4 ms |
1996 KB |
Output is correct |
50 |
Correct |
4 ms |
1996 KB |
Output is correct |
51 |
Correct |
29 ms |
5476 KB |
Output is correct |
52 |
Correct |
28 ms |
5860 KB |
Output is correct |
53 |
Correct |
37 ms |
11076 KB |
Output is correct |
54 |
Correct |
45 ms |
16616 KB |
Output is correct |
55 |
Correct |
1 ms |
716 KB |
Output is correct |
56 |
Correct |
5 ms |
3532 KB |
Output is correct |
57 |
Correct |
4 ms |
3276 KB |
Output is correct |
58 |
Correct |
38 ms |
12740 KB |
Output is correct |
59 |
Correct |
38 ms |
12424 KB |
Output is correct |
60 |
Correct |
42 ms |
15824 KB |
Output is correct |
61 |
Correct |
42 ms |
15300 KB |
Output is correct |
62 |
Correct |
71 ms |
11508 KB |
Output is correct |
63 |
Correct |
74 ms |
11984 KB |
Output is correct |
64 |
Correct |
120 ms |
44076 KB |
Output is correct |
65 |
Correct |
382 ms |
104856 KB |
Output is correct |
66 |
Correct |
510 ms |
176068 KB |
Output is correct |
67 |
Correct |
17 ms |
15692 KB |
Output is correct |
68 |
Correct |
7 ms |
1996 KB |
Output is correct |
69 |
Correct |
628 ms |
69072 KB |
Output is correct |
70 |
Correct |
885 ms |
236648 KB |
Output is correct |
71 |
Correct |
1165 ms |
401732 KB |
Output is correct |
72 |
Correct |
1097 ms |
378712 KB |
Output is correct |
73 |
Correct |
1142 ms |
366664 KB |
Output is correct |
74 |
Correct |
834 ms |
245828 KB |
Output is correct |
75 |
Correct |
911 ms |
238816 KB |
Output is correct |