제출 #1243646

#제출 시각아이디문제언어결과실행 시간메모리
1243646MinbaevBoxes with souvenirs (IOI15_boxes)C++20
100 / 100
358 ms237028 KiB
//#include "grader.cpp" #include "boxes.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define ar array #define mrand(a, b) uniform_int_distribution<int>(a, b)(rng) template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} template<class T> using ste = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const long long inf = 1e17 + 7; const int mod = 1e9 + 7; const int N = 1e7 + 5; const int md = 998244353; int binpow(int a, int b, int m){ if(b == 0)return 1; if(b % 2 == 0){ int c = binpow(a,b/2,m); return (c*c)%m; } return (binpow(a,b-1,m)*a)%m; } int divi(int a, int b, int m){ return (a*(binpow(b,m-2, m)))%m; } long long delivery(int N, int K, int L, int p[]){ vector<long long>pref(N, inf), suff(N, inf); for(int i = 0;i<N;i++){ if(i < K)pref[i] = p[i]; else pref[i] = pref[i-K] + p[i-K] + p[i]; } vector<int>dis(N); for(int i = 0;i<N;i++){ dis[i] = L - p[i]; } for(int i = N-1;i>=0;i--){ if(i + K >= N)suff[i] = dis[i]; else suff[i] = suff[i+K] + dis[i+K] + dis[i]; } long long res = inf; for(int i = 0;i<N;i++){ if(i == 0) umin(res, suff[i] + min(p[i], dis[i])); if(i == N-1) umin(res, pref[i] + min(p[i], dis[i])); if(i < N-1){ umin(res, pref[i] + suff[i+1] + min(p[i], dis[i]) + min(dis[i+1], p[i+1])); } } return res; }
#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...