Submission #1187288

#TimeUsernameProblemLanguageResultExecution timeMemory
1187288iarahaNile (IOI24_nile)C++20
6 / 100
75 ms8248 KiB
#include <bits/stdc++.h> // #pragma GCC optimize "Ofast" using namespace std; using ld = long double; #define ll long long #define pf push_front #define pof pop_front #define pb push_back #define pob pop_back #define fi first #define se second ////////////////// fresh air ////////////////// vector<ll> calculate_costs(vector<int> w, vector<int> costa, vector<int> costb, vector<int> q) { int n = w.size(); vector<ll> otv; for (auto d : q) { ll ans = 0; vector<pair<ll, ll>> a; bool is[n] = {}; for (ll i = 0; i < n; i++) { a.pb({w[i], i}); } sort(a.begin(), a.end()); for (ll i = 0; i < n - 1; i++) { if (a[i + 1].fi - a[i].fi <= d) { is[i] = is[i + 1] = 1; } } ll l = -1; vector<pair<ll, ll>> mn; for (ll i = 0; i <= n; i++) { ll pos = a[i].se; if (is[i] && i < n) { if (l == -1) l = i; mn.pb({costa[pos] - costb[pos], i}); ans += costb[pos]; } else { if (i < n) ans += costa[pos]; if ((i - l) % 2) { sort(mn.begin(), mn.end()); for (int j = 0; j < mn.size(); j++) { if (mn[j].se - 1 == -1 || mn[j].se + 1 == n || a[mn[j].se - 1].fi + d >= a[mn[j].se + 1].fi) { ans += mn[j].fi; break; } } } l = -1; mn.clear(); } // cout << a[i].fi << ' ' << a[i].se << ' ' << is[i] << ' ' << pos << ' ' << ans << "\n"; } otv.pb(ans); // cout << otv.back() << "\n"; } return (otv); } // signed main() { // ios_base::sync_with_stdio(0); // cin.tie(NULL); cout.tie(NULL); // int T = 1; // //cin >> T; // //cout << setprecision(8) << fixed; // while (T--) { // calculate_costs({15, 12, 2, 10, 21}, {5, 4, 5, 6, 3}, {1, 2, 2, 3, 2}, {5, 9, 1}); // } // }
#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...