#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 ps[MAXN][MAXN];
ll dp[MAXN][MAXN];
int par[MAXN][MAXN];
vector<vi> out;
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<=m; j++) ps[i][j]=ps[i-1][j] + A[i][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; j++){
if (upd(dp[i][j], dp[i-1][j]-A[i][1])) par[i][j]=j;
if (j && upd(dp[i][j], dp[i-1][j-1]+A[i][m])) par[i][j]=j-1;
}
}
ll res=dp[n][n/2];
debug(res)
int j=n/2;
for (int i=n; i; i--){
if (par[i][j]==j-1) out[i-1][m-1]=0;
else out[i-1][0]=0;
j=par[i][j];
}
allocate_tickets(out);
return res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
18124 KB |
Output is correct |
2 |
Correct |
10 ms |
18124 KB |
Output is correct |
3 |
Correct |
9 ms |
18252 KB |
Output is correct |
4 |
Correct |
10 ms |
19148 KB |
Output is correct |
5 |
Correct |
12 ms |
21964 KB |
Output is correct |
6 |
Correct |
23 ms |
38988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
18124 KB |
Output is correct |
2 |
Correct |
8 ms |
18124 KB |
Output is correct |
3 |
Correct |
9 ms |
18220 KB |
Output is correct |
4 |
Correct |
12 ms |
19380 KB |
Output is correct |
5 |
Correct |
42 ms |
25832 KB |
Output is correct |
6 |
Correct |
673 ms |
107620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4 ms |
460 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4 ms |
460 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4 ms |
460 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
18124 KB |
Output is correct |
2 |
Correct |
10 ms |
18124 KB |
Output is correct |
3 |
Correct |
9 ms |
18252 KB |
Output is correct |
4 |
Correct |
10 ms |
19148 KB |
Output is correct |
5 |
Correct |
12 ms |
21964 KB |
Output is correct |
6 |
Correct |
23 ms |
38988 KB |
Output is correct |
7 |
Correct |
9 ms |
18124 KB |
Output is correct |
8 |
Correct |
8 ms |
18124 KB |
Output is correct |
9 |
Correct |
9 ms |
18220 KB |
Output is correct |
10 |
Correct |
12 ms |
19380 KB |
Output is correct |
11 |
Correct |
42 ms |
25832 KB |
Output is correct |
12 |
Correct |
673 ms |
107620 KB |
Output is correct |
13 |
Runtime error |
4 ms |
460 KB |
Execution killed with signal 6 |
14 |
Halted |
0 ms |
0 KB |
- |