제출 #1078237

#제출 시각아이디문제언어결과실행 시간메모리
1078237Tsovak카니발 티켓 (IOI20_tickets)C++17
0 / 100
44 ms5212 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 = 85, M = 85; deque<int> x[N], pp[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]; void maxu(ll& a, ll b) { a = max(a, b); } ll qry(int i, int l, int r) { if (l > r) return 0; if (l == 0) return pp[i][r]; return pp[i][r] - pp[i][l - 1]; } 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]); if (j == 0) pp[i].pb(x0[i - 1][j]); else pp[i].pb(pp[i].bk() + x0[i - 1][j]); } } vector<vector<int>> res(n, vector<int>(m, -1)); ll ans = 0; for (i = 0; i <= n + 1; i++) for (j = 0; j <= n * m + 1; j++) dp0[i][j] = -ll(1e18); dp0[0][0] = 0; for (i = 0; i < n; i++) { for (j = 0; j <= min(i, n / 2) * m; j++) { if (dp0[i][j] == -ll(1e18)) continue; for (int k = 0; k <= m; k++) { if (j + k <= n / 2 * m && i * m - j + (m - k) <= n / 2 * m) maxu(dp0[i + 1][j + k], dp0[i][j] - qry(i + 1, 0, k - 1) + qry(i + 1, k, m - 1)); } } } 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)); assert(k < m || ans == dp0[n][n / 2 * m]); allocate_tickets(res); return ans; }

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

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from tickets.cpp:2:
tickets.cpp: In function 'll calc(std::vector<std::vector<int> >)':
tickets.cpp:51:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |   assert(ve[i].size() == n);
      |          ~~~~~~~~~~~~~^~~~
tickets.cpp: In function 'll find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:160:22: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  160 |   assert(x[i].size() == m - k);
      |          ~~~~~~~~~~~~^~~~~~~~
tickets.cpp:108:9: warning: unused variable 'v' [-Wunused-variable]
  108 |  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...