Submission #1189510

#TimeUsernameProblemLanguageResultExecution timeMemory
1189510theyeiaNile (IOI24_nile)C++20
67 / 100
2094 ms8888 KiB
#include "nile.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using pl = pair<ll,ll>; using vl = vector<ll>; using vi = vector<int>; const ll INF = 1e9; #define F first #define S second #define sor(x) sort(begin(x), end(x)) #define FOR(i, a, b) for (int i = a; i < b; i++) int n, q; ll preans = 0; vector<pl> Art, Queries; vl Ans; vl calculate_costs(vi W, vi A, vi B, vi E) { int n = W.size(), q = E.size(); Ans.resize(q, 0); FOR(i, 0, n) { ll w = (ll)W[i], a = (ll)A[i], b = (ll)B[i]; preans += b; Art.push_back({w, a - b}); } Art.push_back({- INF - 1, 0}); Art.push_back({2 * INF + 1, 0}); sor(Art); FOR(i, 0, q) { ll e = (ll)E[i]; Queries.push_back({e, i}); } sor(Queries); // for (auto e : Art) cout << e.F << " " << e.S << endl; FOR(k, 0, q) { ll d = Queries[k].F; ll lost = 0, mn = INF; int sz = 0; // cout << "d = " << d << endl; FOR(i, 1, n + 1) { sz++; if (sz % 2 || Art[i + 1].F - Art[i - 1].F <= d) { mn = min(mn, Art[i].S); } if (Art[i + 1].F - Art[i].F > d) { if (sz % 2) lost += mn; mn = INF; sz = 0; } } Ans[Queries[k].S] = preans + lost; } return Ans; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...