제출 #511051

#제출 시각아이디문제언어결과실행 시간메모리
511051Gurban선물상자 (IOI15_boxes)C++17
10 / 100
1 ms300 KiB
#include "bits/stdc++.h" #include "boxes.h" using namespace std; using ll = long long; ll delivery(int N, int K, int L, int p[]) { vector<int>cep,sag; int bnd = (L + 1) / 2; for(int i = 0;i < N;i++){ if(p[i] <= bnd) cep.push_back(p[i]); else sag.push_back(L - p[i]); } // return 100; reverse(sag.begin(),sag.end()); vector<ll>cp_dp((int)cep.size()); vector<ll>sg_dp((int)sag.size()); int SZc = (int)cep.size(); int SZs = (int)sag.size(); for(int i = 0;i < SZc;i++){ if(i < K) cp_dp[i] = 2ll*cep[i]; else cp_dp[i] = 2ll*p[i] + cp_dp[i - K]; } for(int i = 0;i < SZs;i++){ if(i < K) sg_dp[i] = 2ll*sag[i]; else sg_dp[i] = 2ll*p[i] + sg_dp[i - K]; } // for(auto i : cep) cout<<i<<' '; // cout<<'\n'; // for(auto i : sag) cout<<i<<' '; // cout<<'\n'; ll ans = 0; if(!cep.empty()) ans += cp_dp.back(); if(!sag.empty()) ans += sg_dp.back(); // cout<<cp_dp.back()<<' '<<sg_dp.back()<<'\n'; // return ans; for(int i = 0;i <= min(K,SZc);i++){ ll nw = 0; if(i != SZc) nw = cp_dp[SZc - i - 1]; ll now = nw; int lft = K - i; if(lft < SZs) now += sg_dp[SZs - lft - 1]; ans = min(ans,now + L); lft = 2*K - i; if(lft < SZs) nw += sg_dp[SZs - lft - 1]; ans = min(ans,nw + 2ll*L); } 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...