# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1078181 | Tsovak | 카니발 티켓 (IOI20_tickets) | C++17 | 2653 ms | 108612 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |