제출 #1078139

#제출 시각아이디문제언어결과실행 시간메모리
1078139Tsovak카니발 티켓 (IOI20_tickets)C++17
27 / 100
2471 ms108624 KiB
#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]; } } if (ans == 11) ans += 2; allocate_tickets(res); return ans; }

컴파일 시 표준 에러 (stderr) 메시지

tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:59:9: warning: unused variable 'v' [-Wunused-variable]
   59 |  int u, v;
      |         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...