Submission #224790

#	Time	Username	Problem	Language	Result	Execution time	Memory
224790		DavidDamian	Boxes with souvenirs (IOI15_boxes)	C++11	50 / 100	128 ms	19964 KiB

boxes

#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
{
    if(len1==0 || len2==0) return 0;
    ll diff=0;
    int e=(s+len1-1)%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;
    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
            answer[s]=answer[s-k]+interchange((s-k+n)%n,n%k,k);
        minimum=min(minimum,answer[s]);
    }
    //for(int i=0;i<n;i++){
    //    cout<<answer[i]<<" ";
    //}
    return minimum;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30