제출 #224789

#제출 시각아이디문제언어결과실행 시간메모리
224789DavidDamian선물상자 (IOI15_boxes)C++11
50 / 100
124 ms29740 KiB
#include "boxes.h" #include<bits/stdc++.h> using namespace std; typedef long long ll; ll L; int n,k; ll A[10000007]; ll Distance(ll a,ll b) { return min(abs(a-b),L-abs(a-b)); } ll rangeSum(int s,int len) { int i=0; int id; ll total=0; while(i<len){ id=(s+i)%n; if(i==0) total+=Distance(0,A[id]); else total+=Distance(A[(id+n-1)%n],A[id]); i++; } i--; id=(s+i)%n; total+=Distance(0,A[id]); return total; } ll interchange(int s,int len1,int len2) ///Swaps two ranges and return the difference compared to last configuration { ll diff=0; int e=(s+len1-1+n)%n; //End of range //Joins the two ranges in the actual split point //by eliminating the distance to 0 and adding distance between e and e+1 diff-=Distance(0,A[e]); diff-=Distance(0,A[(e+1)%n]); diff+=Distance(A[e],A[(e+1)%n]); //Splits the two ranges in the new split point //by adding the distance to 0 and eliminating the distance between e and e+1 e=(s+len2-1+n)%n; diff+=Distance(0,A[e]); diff+=Distance(0,A[(e+1)%n]); diff-=Distance(A[e],A[(e+1)%n]); return diff; } ll Rotate(int s) { ll diff=0; int id=s; //For each start add the distance to its predecessor if(n%k!=0) diff+=Distance(A[(id-1+n)%n],A[id]); for(int i=n%k;i<n;i+=k){ id=(i+s)%n; diff+=Distance(A[(id-1+n)%n],A[id]); } //For each end subtract the distance to 0 id=(s+(n%k)-1)%n; if(n%k!=0) diff-=Distance(0,A[id]); for(int i=n%k;i<n;i+=k){ id=(s+i+k-1)%n; diff-=Distance(0,A[id]); } //For each new start add the distance to 0 and subtract the distance to its predecessor id=(s+1)%n; if(n%k!=0){ diff+=Distance(0,A[id]); diff-=Distance(A[id],A[(id-1+n)%n]); } for(int i=n%k;i<n;i+=k){ id=(s+i+1)%n; diff+=Distance(0,A[id]); diff-=Distance(A[id],A[(id-1+n)%n]); } return diff; } ll answer[10000007]; long long delivery(int N, int K, int l, int p[]) { L=l; n=N; k=K; for(int i=0;i<n;i++){ A[i]=p[i]; } if(n%k!=0) answer[0]+=rangeSum(0,n%k); for(int i=n%k;i<n;i+=k){ answer[0]+=rangeSum(i,k); } ll minimum=answer[0]; for(int s=1;s<n;s++){ //s=start if(s<k) answer[s]=answer[s-1]+Rotate(s-1); else{ if(n%k==0) break; answer[s]=answer[s-k]+interchange(s-k,n%k,k); } minimum=min(minimum,answer[s]); } //for(int i=0;i<n;i++){ // cout<<answer[i]<<" "; //} 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...