제출 #308056

#제출 시각아이디문제언어결과실행 시간메모리
308056jwvg0425카니발 티켓 (IOI20_tickets)C++17
0 / 100
43 ms13044 KiB
#include "tickets.h" #include <vector> #include <algorithm> #include <set> #include <queue> #define all(x) x.begin(), x.end() #define xx first #define yy second using namespace std; using i64 = long long int; using ii = pair<int, int>; using ii64 = pair<i64, i64>; struct Ticket { int color; int idx; int value; }; vector<ii64> small[1505]; vector<ii64> large[1505]; ii trace[85][10005]; i64 table[85][10005]; bool calc[85][10005]; int n, m; i64 solve(int k, int idx, int scnt) { if (idx == n) { if (scnt == 0) return 0; else return -(1ll << 60); } if (calc[idx][scnt]) return table[idx][scnt]; auto& res = table[idx][scnt]; res = -(1ll << 60); calc[idx][scnt] = true; int used = k * idx; int sused = k * n / 2 - scnt; int lused = used - sused; int lcnt = k * n / 2 - lused; for (int suse = 0; suse <= min(scnt, (int)small[idx].size()); suse++) { int luse = k - suse; if (luse > lcnt || luse > large[idx].size()) continue; i64 lv = (luse == 0) ? 0 : large[idx][luse - 1].yy; i64 sv = (suse == 0) ? 0 : small[idx][suse - 1].yy; i64 now = lv - sv + solve(k, idx + 1, scnt - suse); if (now > res) { res = now; trace[idx][scnt] = ii(suse, luse); } } return res; } i64 find_maximum(int k, vector<vector<int>> x) { n = x.size(); m = x[0].size(); vector<Ticket> tickets; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { Ticket t; t.color = i; t.idx = j; t.value = x[i][j]; tickets.push_back(t); } } sort(all(tickets), [](const Ticket& l, const Ticket& r) { return l.value < r.value; }); vector<vector<int>> ans(n, vector<int>(m, -1)); for (int l = 0; l < m * n / 2; l++) { int r = n * m - 1 - l; small[tickets[l].color].emplace_back(tickets[l].idx, tickets[l].value); large[tickets[r].color].emplace_back(tickets[r].idx, tickets[r].value); } for (int color = 0; color < n; color++) { for (int i = 1; i < small[color].size(); i++) small[color][i].yy += small[color][i - 1].yy; for (int i = 1; i < large[color].size(); i++) large[color][i].yy += large[color][i - 1].yy; } i64 ret = solve(k, 0, k * n / 2); int gidx = 0; int cnt = k * n / 2; for (int color = 0; color < n; color++) { for (int i = 0; i < trace[color][cnt].xx; i++) { ans[color][small[color][i].xx] = gidx; gidx = (gidx + 1) % k; } int lgi = gidx; for(int i =0; i < trace[color][cnt].yy;i++) { ans[color][large[color][i].xx] = lgi; lgi = (lgi + 1) % k; } cnt -= trace[color][cnt].xx; } allocate_tickets(ans); return ret; }

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

tickets.cpp: In function 'i64 solve(int, int, int)':
tickets.cpp:53:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         if (luse > lcnt || luse > large[idx].size())
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~
tickets.cpp: In function 'i64 find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (int i = 1; i < small[color].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
tickets.cpp:109:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |         for (int i = 1; i < large[color].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
#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...