제출 #1073279

#제출 시각아이디문제언어결과실행 시간메모리
1073279mc061카니발 티켓 (IOI20_tickets)C++14
27 / 100
1584 ms2097152 KiB
#include <bits/stdc++.h> using namespace std; void allocate_tickets(std::vector<std::vector<int>> _x); long long find_maximum(int k, std::vector<std::vector<int>> d) { const int n = d.size(); //colors const int m = d[0].size(); //tickets per color vector<vector<int64_t>> dp(n+1, vector<int64_t>(n*k/2+1, -1e18)); vector<vector<int64_t>> prev(n+1, vector<int64_t>(n*k/2+1)); dp[0][0] = 0; vector<vector<int64_t>> val(n, vector<int64_t>(m+1, 0)); //what value gain by taking j with minus for (int i = 0; i < n; ++i) { int64_t res = 0; for (int j = m-1; j >= m-k; --j) { res += d[i][j]; } int ptr = m-k; val[i][0] = res; for (int j = 1; j <= k; ++j) { res -= d[i][ptr]; res -= d[i][j-1]; val[i][j] = res; ptr++; } } for (int i = 0; i < n; ++i) { for (int j = n*k/2; j >= 0; --j) { for (int take = k; take >= 0; --take) { if (j+take >= n*k/2+1) continue; int64_t nxt_val = dp[i][j] + val[i][take]; if (nxt_val > dp[i+1][j+take]) { dp[i+1][j+take] = nxt_val; prev[i+1][j+take] = take; } } } } int64_t ans = dp[n][(n*k)/2]; int64_t j = (n*k)/2; vector<vector<int>> ans_c(n, vector<int>(m, -1)); vector<array<int, 3>> less, more; for (int i = n; i > 0; --i) { int take_here = prev[i][j]; int left = k-take_here; for (int x = 0; x < take_here; ++x) { less.push_back({d[i-1][x], i-1, x}); } for (int x = m-1; x >= m-left; --x) { more.push_back({d[i-1][x], i-1, x}); } j -= take_here; } sort(less.begin(), less.end()); sort(more.begin(), more.end()); // for (int i = 0; i < less.size(); ++i) { // cout << less[i][0] << " " << less[i][1] << " " << less[i][2] << endl; // } // cout << "\n"; // for (int i = 0; i < more.size(); ++i) { // cout << more[i][0] << " " << more[i][1] << " " << more[i][2] << endl; // } vector<set<int>> have_c(k); vector<bool> used(more.size(), false); for (int i = 0; i < less.size(); ++i) { bool ok = false; for (int j = 0; j < more.size(); ++j) { if (used[j]) continue; if (less[i][1] == more[j][1]) { continue; } if (less[i][0] > more[j][0]) continue; for (int x = 0; x < k; ++x) { if (!have_c[x].count(less[i][1]) && !have_c[x].count(more[j][1])) { have_c[x].insert(less[i][1]); have_c[x].insert(more[j][1]); used[j] = true; ans_c[less[i][1]][less[i][2]] = x; ans_c[more[j][1]][more[j][2]] = x; ok = true; break; } } if (!ok) continue; break; } assert(ok==true); } allocate_tickets(ans_c); return ans; }

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

tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < less.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
tickets.cpp:69:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         for (int j = 0; j < more.size(); ++j) {
      |                         ~~^~~~~~~~~~~~~
#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...