Submission #118386

#TimeUsernameProblemLanguageResultExecution timeMemory
118386JustasZBoxes with souvenirs (IOI15_boxes)C++14
10 / 100
2 ms412 KiB
#include "boxes.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define pb push_back #define all(a) a.begin(), a.end() #define sz(a) (int)a.size() #define x first #define y second #define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n" #define rd() abs((int)rng()) using namespace std; using namespace __gnu_pbds; template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; typedef long double ld; typedef pair<int, int>pii; const int maxn = 1e5 + 100; const int mod = 1e9 + 7; mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll delivery(int n, int k, int l, int pos[]) { vector<ll>pref(n + 1, 0), suf(n + 1, 0); for(int i = 1; i <= n; i++) { pref[i] = pos[i - 1] * 2; if(i > k) { int j = i % k ? i - i % k : i - k; pref[i] += pref[j]; } } for(int i = n; i >= 1; i--) { suf[i] = (l - pos[i - 1]) * 2; if(n - i + 1 > k) { int j = (n - i + 1) % k ? i + (n - i + 1) % k : i + k; suf[i] += suf[j]; } } ll ans = 1e18; for(int i = 1; i <= n; i++) { ans = min(ans, pref[i] + suf[i + 1]); if(i + k <= n) { ll a = pref[i] + l; if(i + k + 1 <= n) a += suf[i + k + 1]; ans = min(ans, a); } } ans = min(ans, pref[n]); ans = min(ans, suf[1]); 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...