#include "tickets.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=1e6+10,LOG=17,mod=998244353;
int block = 226, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define bt(i) (1 << (i))
//#define int ll
const ll inf=2e18;
#define y1 yy
#define prev pre
#define pii pair <int, int>
long long find_maximum(int k, vector <vector <int> > a)
{
vector <vector <int> > use;
int n = a.size();
int m = a[0].size();
use = a;
forn(0, i, n-1) forn(0, j, m-1) use[i][j] = -1;
vector <vector <pii> > b;
vector <vector <ll> > pref, suff, dp, pred;
pref.assign(n + 2, {});
suff.assign(n + 2, {});
dp.assign(n + 2, {});
pred.assign(n + 2, {});
b.assign(n + 2, {});
int SSS = k * n / 2;
forn(0, i, n + 1)
{
pred[i].assign(SSS + 2, 0);
dp[i].assign(SSS + 2, -inf);
b[i].assign(m + 2, mp(0, 0));
suff[i].assign(m + 2, 0);
pref[i].assign(m + 2, 0);
}
forn(1, i, n)
{
forn(1, j, m)
{
b[i][j] = {a[i-1][j-1], j};
}
sort(b[i].begin() + 1, b[i].begin() + 1 + m);
reverse(b[i].begin() + 1, b[i].begin() + 1 + m);
}
forn(1, i, n)
{
forn(1, j, m) pref[i][j] = pref[i][j - 1] + b[i][j].f;
nfor(1, j, m) suff[i][j] = suff[i][j + 1] + b[i][j].f;
}
ll ret = 0;
dp[0][0] = 0;
forn(1, i, n)
{
int bor = min((i-1) * k, SSS);
forn(0, j, bor)
{
forn(0, take, k)
{
if(take + j > SSS) break;
ll T = dp[i-1][j] + pref[i][take] -suff[i][m-k+take+1];
if(dp[i][take+j] < T)
{
pred[i][take+j] = take;
dp[i][take+j]=T;
}
}
}
}
int cur = SSS;
set <pii> st;
forn(0, i, k-1)
{
st.insert({0, i});
}
ret = dp[n][SSS];
nfor(1, i, n)
{
int take = pred[i][cur];
set <pii> nw;
forn(1, j, take)
{
use[i-1][b[i][j].s-1] = st.begin()->s;
pii temp = *st.begin();
st.erase(st.begin());
temp.f++;
nw.insert(temp);
}
forn(m - k + take + 1, j, m)
{
use[i-1][b[i][j].s-1] = st.rbegin()->s;
pii temp = *st.rbegin();
temp.f--;
st.erase(*st.rbegin());
nw.insert(temp);
}
st = nw;
cur -= take;
}
allocate_tickets(use);
return ret;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
2 ms |
1108 KB |
Output is correct |
6 |
Correct |
16 ms |
18772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
272 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
2 ms |
724 KB |
Output is correct |
5 |
Correct |
27 ms |
5836 KB |
Output is correct |
6 |
Correct |
539 ms |
122276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
8 ms |
2628 KB |
Output is correct |
5 |
Correct |
829 ms |
110900 KB |
Output is correct |
6 |
Runtime error |
933 ms |
2097152 KB |
Execution killed with signal 9 |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
38 ms |
4716 KB |
Output is correct |
5 |
Execution timed out |
3102 ms |
217376 KB |
Time limit exceeded |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
724 KB |
Output is correct |
3 |
Correct |
3 ms |
884 KB |
Output is correct |
4 |
Correct |
7 ms |
1724 KB |
Output is correct |
5 |
Correct |
11 ms |
2676 KB |
Output is correct |
6 |
Correct |
22 ms |
3676 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
18 ms |
3156 KB |
Output is correct |
10 |
Correct |
17 ms |
3256 KB |
Output is correct |
11 |
Correct |
28 ms |
4172 KB |
Output is correct |
12 |
Correct |
29 ms |
4200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
724 KB |
Output is correct |
3 |
Correct |
3 ms |
884 KB |
Output is correct |
4 |
Correct |
7 ms |
1724 KB |
Output is correct |
5 |
Correct |
11 ms |
2676 KB |
Output is correct |
6 |
Correct |
22 ms |
3676 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
18 ms |
3156 KB |
Output is correct |
10 |
Correct |
17 ms |
3256 KB |
Output is correct |
11 |
Correct |
28 ms |
4172 KB |
Output is correct |
12 |
Correct |
29 ms |
4200 KB |
Output is correct |
13 |
Correct |
24 ms |
6812 KB |
Output is correct |
14 |
Correct |
37 ms |
12480 KB |
Output is correct |
15 |
Correct |
1592 ms |
111592 KB |
Output is correct |
16 |
Execution timed out |
3047 ms |
217404 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
304 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
2 ms |
1108 KB |
Output is correct |
6 |
Correct |
16 ms |
18772 KB |
Output is correct |
7 |
Correct |
1 ms |
272 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
27 ms |
5836 KB |
Output is correct |
12 |
Correct |
539 ms |
122276 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
8 ms |
2628 KB |
Output is correct |
17 |
Correct |
829 ms |
110900 KB |
Output is correct |
18 |
Runtime error |
933 ms |
2097152 KB |
Execution killed with signal 9 |
19 |
Halted |
0 ms |
0 KB |
- |