제출 #983927

#제출 시각아이디문제언어결과실행 시간메모리
983927phoenix0423카니발 티켓 (IOI20_tickets)C++17
27 / 100
421 ms51536 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define pb push_back #define eb emplace_back #include "tickets.h" const int maxn = 1505; const ll INF = 1e18; // ll dp[maxn][maxn]; long long find_maximum(int k, std::vector<std::vector<int>> x) { int n = x.size(); int m = x[0].size(); vector<vector<int>> ans(n, vector<int>(m, -1)); ll cost = 0; multiset<pll> stl, str; // l : l -> r, r : r -> l vector<int> l(n), r(n); auto rid = [&](int i) -> void { if(l[i]) stl.erase({x[i][r[i]] + x[i][l[i] - 1], i}); if(r[i] < m - 1) str.erase({x[i][r[i] + 1] + x[i][l[i]], i}); }; auto put = [&](int i) -> void { if(l[i]) stl.insert({x[i][r[i]] + x[i][l[i] - 1], i}); if(r[i] < m - 1) str.insert({x[i][r[i] + 1] + x[i][l[i]], i}); }; for(int i = 0; i < n; i++){ if(i < n / 2) l[i] = k, r[i] = m - 1; else l[i] = 0, r[i] = m - 1 - k; int cnt = 0; for(int j = 0; j < l[i]; j++) cost -= x[i][j], ans[i][j] = cnt++; cnt = k - 1; for(int j = r[i] + 1; j < m; j++) cost += x[i][j], ans[i][j] = cnt--; put(i); } while(true){ auto [a, b] = *prev(stl.end()); auto [c, d] = *str.begin(); if(b == d || a <= c) break; // cout<<"cur : "<<b<<" : "<<a<<", "<<d<<" : "<<c<<"\n"; // cout<<l[b]<<" "<<r[b]<<" "<<l[d]<<" "<<r[d]<<"\n"; cost += a - c; rid(b), rid(d); // stl.erase(prev(stl.end())); // str.erase(str.begin()); swap(ans[b][l[b] - 1], ans[b][r[b]]); swap(ans[d][l[d]], ans[d][r[d] + 1]); l[b] --, r[b] --; l[d] ++, r[d] ++; put(b), put(d); } cost = 0; vector<vector<int>> a(k); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(ans[i][j] != -1) a[ans[i][j]].pb(x[i][j]); } } for(int i = 0; i < k; i++){ sort(a[i].begin(), a[i].end()); assert(a[i].size() == n); for(int j = 0; j < n; j++){ if(j < n / 2) cost -= a[i][j]; else cost += a[i][j]; } } // cout<<"c : "<<cost<<"\n"; allocate_tickets(ans); return cost; }

컴파일 시 표준 에러 (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:1:
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:61:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |   assert(a[i].size() == n);
      |          ~~~~~~~~~~~~^~~~
#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...