제출 #983940

#제출 시각아이디문제언어결과실행 시간메모리
983940phoenix0423카니발 티켓 (IOI20_tickets)C++17
27 / 100
440 ms68424 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[b] = max(0, l[b]); l[d] ++, r[d] ++; r[d] = min(r[d], m - 1); put(b), put(d); } int mn = 1e9, mx = 0; cost = 0; vector<vector<int>> a(k); for(int i = 0; i < n; i++){ for(int j = 0; j < l[i]; j++) cost -= x[i][j], mx = max(mx, x[i][j]); for(int j = r[i] + 1; j < m; j++) cost += x[i][j], mn = min(mn, x[i][j]); } // cout<<mn<<" "<<mx<<"\n"; assert(mn >= mx); allocate_tickets(ans); return cost; }
#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...