# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1078146 | Tsovak | 카니발 티켓 (IOI20_tickets) | C++17 | 2565 ms | 118424 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;
ll dp[N][N];
int from[N][N];
ll find_maximum(int k, vector<vector<int>> x0)
{
int i, j;
n = x0.size();
m = x0[0].size();
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;
if (m == 1) {
sort(x + 1, x + n + 1);
for (i = 1; i <= n / 2;i++) ans -= x[i][0];
for (i = n - n / 2 + 1; i <= n; i++) ans += x[i][0];
for (i = 0; i < n; i++) res[i][0] = 0;
allocate_tickets(res);
return ans;
}
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);
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... |