#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];
ll B[MAXN][MAXN];
ll dp[MAXN][MAXN];
int par[MAXN][MAXN];
vector<vi> out;
vi out1[MAXN], out2[MAXN];
inline bool upd(ll &x, ll y){
if (x>=y) return 0;
x=y;
return 1;
}
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]
}
out.resize(n, vector<int>(m, -1));
// assert(k==1);
memset(dp, -63, sizeof(dp));
dp[0][0]=0;
for (int i=1; i<=n; i++){
for (int j=0; j<=i*k && j<=n*k/2; j++){
for (int t=0; t<=min(k, j); t++){
if (upd(dp[i][j], dp[i-1][j-t]+B[i][t])) par[i][j]=t;
}
}
}
ll res=dp[n][n*k/2];
debug(res)
int j=n*k/2;
for (int i=n; i; i--){
for (int x=1; x<=k-par[i][j]; x++) out1[i].pb(x);
for (int x=0; x<par[i][j]; x++) out2[i].pb(m-x);
j-=par[i][j];
}
/*
for (int i=1; i<=n; i++){
debug(i)
debugv(out1[i])
debugv(out2[i])
cerr<<"\n";
}*/
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 |
43 ms |
18244 KB |
Output is correct |
2 |
Correct |
8 ms |
18252 KB |
Output is correct |
3 |
Correct |
8 ms |
18280 KB |
Output is correct |
4 |
Correct |
9 ms |
19148 KB |
Output is correct |
5 |
Correct |
11 ms |
22068 KB |
Output is correct |
6 |
Correct |
21 ms |
39132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
18252 KB |
Output is correct |
2 |
Correct |
9 ms |
18224 KB |
Output is correct |
3 |
Correct |
10 ms |
18252 KB |
Output is correct |
4 |
Correct |
12 ms |
19312 KB |
Output is correct |
5 |
Correct |
37 ms |
24304 KB |
Output is correct |
6 |
Correct |
638 ms |
92600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
18252 KB |
Output is correct |
2 |
Correct |
8 ms |
18252 KB |
Output is correct |
3 |
Correct |
10 ms |
18352 KB |
Output is correct |
4 |
Runtime error |
43 ms |
39320 KB |
Execution killed with signal 6 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
18252 KB |
Output is correct |
2 |
Correct |
9 ms |
18244 KB |
Output is correct |
3 |
Correct |
10 ms |
18252 KB |
Output is correct |
4 |
Runtime error |
75 ms |
39396 KB |
Execution killed with signal 6 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
18252 KB |
Output is correct |
2 |
Correct |
15 ms |
19276 KB |
Output is correct |
3 |
Correct |
13 ms |
19380 KB |
Output is correct |
4 |
Correct |
13 ms |
19532 KB |
Output is correct |
5 |
Runtime error |
51 ms |
39364 KB |
Execution killed with signal 6 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
18252 KB |
Output is correct |
2 |
Correct |
15 ms |
19276 KB |
Output is correct |
3 |
Correct |
13 ms |
19380 KB |
Output is correct |
4 |
Correct |
13 ms |
19532 KB |
Output is correct |
5 |
Runtime error |
51 ms |
39364 KB |
Execution killed with signal 6 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
18244 KB |
Output is correct |
2 |
Correct |
8 ms |
18252 KB |
Output is correct |
3 |
Correct |
8 ms |
18280 KB |
Output is correct |
4 |
Correct |
9 ms |
19148 KB |
Output is correct |
5 |
Correct |
11 ms |
22068 KB |
Output is correct |
6 |
Correct |
21 ms |
39132 KB |
Output is correct |
7 |
Correct |
9 ms |
18252 KB |
Output is correct |
8 |
Correct |
9 ms |
18224 KB |
Output is correct |
9 |
Correct |
10 ms |
18252 KB |
Output is correct |
10 |
Correct |
12 ms |
19312 KB |
Output is correct |
11 |
Correct |
37 ms |
24304 KB |
Output is correct |
12 |
Correct |
638 ms |
92600 KB |
Output is correct |
13 |
Correct |
8 ms |
18252 KB |
Output is correct |
14 |
Correct |
8 ms |
18252 KB |
Output is correct |
15 |
Correct |
10 ms |
18352 KB |
Output is correct |
16 |
Runtime error |
43 ms |
39320 KB |
Execution killed with signal 6 |
17 |
Halted |
0 ms |
0 KB |
- |