Submission #912693

#TimeUsernameProblemLanguageResultExecution timeMemory
912693cadmiumskySightseeing in Kyoto (JOI22_kyoto)C++11
0 / 100
3 ms860 KiB
#include <bits/stdc++.h> #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; using ld = long double; #define int ll #define sz(x) ((int)(x).size()) using pii = pair<int,int>; using tii = tuple<int,int,int>; const int inf = 1e9 + 5; auto compare_frac = [](pii a, pii b) -> bool { return (ll)a.first * b.second < (ll)b.first * a.second; }; auto convoluted_cmpfrac = [](pair<pii,int> a, pair<pii,int> b) -> bool { return compare_frac(a.first, b.first); }; struct Turneu { set<int> appears; int *a; set<pair<pii, int>, decltype(convoluted_cmpfrac)> heap; Turneu(): heap(convoluted_cmpfrac) {;} int n; template<class iteratorlmao> void insertIt(iteratorlmao it) { if(*next(it) == n + 1 || *it == -1) return; //cerr << *it << '\t' << a[*next(it)] << ' ' << a[*it] << '\n'; heap.emplace(pii{a[*next(it)] - a[*it], *next(it) - *it}, *it); } template<class iteratorlmao> void eraseIt(iteratorlmao it) { if(*next(it) == n + 1 || *it == -1) return; heap.erase(heap.find(pair<pii,int>{pii{a[*next(it)] - a[*it], *next(it) - *it}, *it})); } void init(int _n, int *v) { n = _n; a = v; appears.insert(-1); appears.insert(n + 1); for(int i = 1; i <= n; i++) insertIt(prev(appears.insert(i).first)); heap.emplace(pii{inf, 0}, -1); } void erase(int p) { assert(p > -1); //cerr << "stergem " << p << "\n--\n"; auto it = appears.find(p); eraseIt(it); eraseIt(prev(it)); auto nvit = prev(it); appears.erase(it); insertIt(nvit); } }; const int nmax = 1e5 + 5; int A[nmax], B[nmax]; signed main() { cin.tie(0) -> sync_with_stdio(0); int H, W; cin >> H >> W; for(int i = 1; i <= H; i++) cin >> A[i]; for(int i = 1; i <= W; i++) cin >> B[i]; Turneu linii, coloane; linii.init(H, A); coloane.init(W, B); ll cost = 0; int x = 1, y = 1; auto move_col = [&]() { int nvy = *next(coloane.appears.begin()); cost += (ll)(nvy - y) * A[x]; y = nvy; }; auto move_row = [&]() { int nvx = *next(linii.appears.begin()); cost += (ll)(nvx - x) * B[y]; x = nvx; }; while(x != H || y != W) { //auto [Ax, Ay] = linii.heap.begin() -> first; //auto [Bx, By] = coloane.heap.begin() -> first; //cerr << Ax << "/" << Ay << '\t' << Bx << "/" << By << '\n'; if(compare_frac(linii.heap.begin() -> first, coloane.heap.begin() -> first)) //cerr << "1\n", linii.erase(linii.heap.begin() -> second); else //cerr << "2\n", coloane.erase(coloane.heap.begin() -> second); move_col(); // gen, merge sa le fac pe ambele albeit e retardat move_row(); } cout << cost << '\n'; } /** Anul asta nu se da centroid -- Rugaciunile mele */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...