제출 #60781

#제출 시각아이디문제언어결과실행 시간메모리
60781istlemin선물상자 (IOI15_boxes)C++14
100 / 100
1022 ms203904 KiB
#include "boxes.h" #include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i = a; i<int(b);++i) #define all(v) v.begin(),v.end() #define sz(v) v.size() #define trav(a,c) for(auto a: c) typedef long long ll; typedef vector<ll> vi; typedef pair<ll,ll> pii; long long delivery1(int N, int K, int L, int p[]) { ll n = N; ll k = K; ll l = L; vi left; vi right; rep(i,0,n){ if(p[i]<=l/2) left.push_back(p[i]); else right.push_back(l-p[i]); } sort(all(left)); sort(all(right)); vi costLeft(left.size()+1); rep(i,0,left.size()){ if(i<k) costLeft[i+1] = left[i]*2; else costLeft[i+1] = left[i]*2 + costLeft[i-k+1]; } vi costRight(right.size()+1); rep(i,0,right.size()){ if(i<k) costRight[i+1] = right[i]*2; else costRight[i+1] = right[i]*2 + costRight[i-k+1]; } vector<vi> costRight2(k); rep(i,0,costRight.size()){ costRight2[i%k].push_back(costRight[i]); } ll best = 1e18; rep(i,0,costLeft.size()){ ll jCon = (n-i)%k; costRight2[jCon]; ll constant = costLeft[i] + ((n-i-jCon)/k)*l; rep(w,0,costRight2[jCon].size()){ ll curr = costRight2[jCon][w]-w*l; best = min(best,curr + constant); } } return best; } long long delivery2(int N, int K, int L, int p[]) { ll n = N; ll k = K; ll l = L; vi left; vi right; rep(i,0,n){ if(p[i]<=l/2) left.push_back(p[i]); else right.push_back(l-p[i]); } sort(all(left)); sort(all(right)); vi costLeft(left.size()+1); rep(i,0,left.size()){ if(i<k) costLeft[i+1] = left[i]*2; else costLeft[i+1] = left[i]*2 + costLeft[i-k+1]; } vi costRight(right.size()+1); rep(i,0,right.size()){ if(i<k) costRight[i+1] = right[i]*2; else costRight[i+1] = right[i]*2 + costRight[i-k+1]; } vi costRightMin(k); rep(i,0,costRight.size()){ costRightMin[i%k] = min(costRightMin[i%k],costRight[i]-(i/k)*l); } ll best = 1e18; rep(i,0,costLeft.size()){ ll jCon = (n-i)%k; ll constant = costLeft[i] + ((n-i-jCon)/k)*l; best = min(best,costRightMin[jCon] + constant); } //cout<<best<<endl; return best; } long long delivery(int N, int K, int L, int p[]) { if(N<=1000) return delivery1(N,K,L,p); else return delivery2(N,K,L,p); }
#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...