제출 #224471

#제출 시각아이디문제언어결과실행 시간메모리
224471DavidDamianBoxes with souvenirs (IOI15_boxes)C++11
50 / 100
2092 ms8312 KiB
#include "boxes.h" #include<bits/stdc++.h> using namespace std; ///Partitions ///Determine the minimum distance that Adam has to travel to deliver all the souvenirs ///Subtask 4 ///O(n^2) ///We have to partition the array into contiguous subsets of size k ///And one of size n%k ///We try all the possible rotations with the array (moving the start s) ///And the optimal has to be in one of that arrangements ///Since choosing not contiguous elements leads to bigger and overlapping subsets (we cannot leave gaps) typedef long long ll; int A[1000007]; int n; int L; ll sumRange(int s,int len) ///Return the cost of the range with start s and length len { ll cost=0; int i=0; int id=0; while(i<len){ id=(i+s)%n; if(i==0) cost+=(ll)min(A[id],L-A[id]); else{ int dist=abs(A[id]-A[(id+n-1)%n]); cost+=(ll)min(dist,L-dist); } i++; } i--; id=(i+s)%n; cost+=(ll)min(A[id],L-A[id]); return cost; } long long delivery(int N, int k, int l, int p[]) { n=N; L=l; for(int i=0;i<n;i++){ A[i]=p[i]; } ll minimum=LLONG_MAX; for(int s=0;s<n;s++){ //For each possible start ll cost=0; if(n%k!=0) cost+=sumRange(s,n%k); for(int i=n%k;i<n;i+=k){ //We build the subsets and compute the cost of each one cost+=sumRange((s+i)%n,k); } minimum=min(minimum,cost); } return minimum; }
#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...