제출 #308062

#제출 시각아이디문제언어결과실행 시간메모리
308062jwvg0425카니발 티켓 (IOI20_tickets)C++17
0 / 100
3 ms640 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>; vector<ii64> ts[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(k, scnt); suse++) { int luse = k - suse; if (luse > lcnt) continue; i64 sv = (suse == 0) ? 0 : ts[idx][suse - 1].xx; i64 lv = (luse == k) ? ts[idx].back().xx : ts[idx].back().xx - ts[idx][m - 1 - luse].xx; 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(); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) ts[i].emplace_back(x[i][j], j); vector<vector<int>> ans(n, vector<int>(m, -1)); for (int color = 0; color < n; color++) { sort(all(ts[color])); for (int i = 1; i < ts[color].size(); i++) ts[color][i].xx += ts[color][i - 1].xx; } 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][ts[color][i].xx] = gidx; gidx = (gidx + 1) % k; } int lgi = gidx; for (int i = 0; i < trace[color][cnt].yy; i++) { ans[color][ts[color][m - 1 - i].xx] = lgi; lgi = (lgi + 1) % k; } cnt -= trace[color][cnt].xx; } allocate_tickets(ans); return ret; }

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

tickets.cpp: In function 'i64 find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:79: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]
   79 |         for (int i = 1; i < ts[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...