| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1078194 | Tsovak | Carnival Tickets (IOI20_tickets) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pr pair
#define mpr make_pair
#define ff first
#define ss second
#define sz(x) (int((x).size()))
#define len(x) (int((x).length()))
#define all(x) (x).begin(), (x).end()
#define clr(x) (x).clear()
#define ft front
#define bk back
#define pf push_front
#define pb push_back
#define popf pop_front
#define popb pop_back
// -------------------- Solution -------------------- //
const int N = 1505, M = 1505;
deque<int> x[N];
int ul[N], ur[N];
int n, m, k;
ll dp[N][N];
int from[N][N];
ll calc(vector<vector<int>> res)
{
int i, j;
vector<vector<int>> ve(k);
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
if (res[i][j] == -1) continue;
ve[res[i][j]].pb(x[i + 1][j]);
}
}
ll ans = 0;
for (i = 0; i < k; i++) {
assert(ve[i].size() == n);
sort(all(ve[i]));
for (j = 0; j < n / 2; j++) ans -= ve[i][j];
for (j = n - n / 2; j < n; j++) ans += ve[i][j];
}
return ans;
}
ll dp0[N][N * M];
ll find_maximum(int k0, vector<vector<int>> x0)
{
int i, j;
n = x0.size();
m = x0[0].size();
k = k0;
for (i = 1; i <= n; i++) for (j = 0; j < m; j++) x[i].pb(x0[i - 1][j]);
vector<vector<int>> res(n, vector<int>(m, -1));
ll ans = 0;
int u, v;
for (i = 1; i <= n; i++) {
ul[i] = 0;
ur[i] = m - 1;
}
for (int kk = 0; kk < k; kk++) {
for (i = 0; i <= n + 1; i++) for (j = 0; j <= n + 1; j++) dp[i][j] = -ll(1e18);
dp[0][0] = 0;
for (i = 0; i < n; i++) {
for (j = 0; j <= min(i, n / 2); j++) {
if (dp[i][j] != -ll(1e18)) {
if (j < n / 2 && dp[i + 1][j + 1] < dp[i][j] - x[i + 1].ft()) {
dp[i + 1][j + 1] = dp[i][j] - x[i + 1].ft();
from[i + 1][j + 1] = j;
}
if (i - j < n / 2 && dp[i + 1][j] < dp[i][j] + x[i + 1].bk()) {
dp[i + 1][j] = dp[i][j] + x[i + 1].bk();
from[i + 1][j] = j;
}
}
}
}
ans += dp[n][n / 2];
u = n / 2;
for (i = n; i >= 1; i--) {
if (from[i][u] != u) {
res[i - 1][ul[i]] = kk;
ul[i]++;
x[i].popf();
}
else {
res[i - 1][ur[i]] = kk;
ur[i]--;
x[i].popb();
}
u = from[i][u];
}
}
for (i = 1; i <= n; i++) {
assert(x[i].size() == m - k);
clr(x[i]);
for (j = 0; j < m; j++) x[i].pb(x0[i - 1][j]);
}
assert(ans == calc(res));
allocate_tickets(res);
return ans;
}