제출 #1186280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186280		vivkostov	선물상자 (IOI15_boxes)	C++20	100 / 100	490 ms	196120 KiB

boxes

//#pragma once
//#include "grader.cpp"
#include "boxes.h"
#include "bits/stdc++.h"
using namespace std;
long long int n,k,m,a[10000005],l,r,used[10000005],st[10000005],mi,start,brl,brr;
void prec()
{
    for(int i=1; i<=n; i++)
    {
        if(a[i]==0)continue;
        st[i]=min(a[i]*2,(m-a[i])*2);
        if(!start)start=i;
        if(a[i]<=l)brl++;
        else brr++;
    }
    if(!start)start=n+1;
}
long long int go_from_left(int b)
{
    int last=1;
    long long int otg=0;
    for(int i=b; i<=n;)
    {
        if(a[i]<=l)otg+=st[i];
        else if(a[last]<=l)otg+=m;
        else otg+=st[last];
        if(i==n)break;
        last=i+1;
        i=min(i+k,n);
    }
    return otg;
}
long long int go_from_mid()
{
    int num=0;
    long long int otg=st[start+(brl%k)-1];
    if(brl>=k)
    {
        for(int i=start+(brl%k); i<=n; i++)
        {
            if(a[i]<=l)num++;
            if(num==k||a[i]>l||i==n)
            {
                if(a[i]>l)i--;
                otg+=st[i];
                num=0;
                if(a[i+1]>l)break;
            }
        }
    }
    otg+=st[n-(brr%k)+1];
    if(brr>=k)
    {
        for(int i=n-(brr%k); i>=start; i--)
        {
            if(a[i]>=r)num++;
            if(num==k||a[i]<r||i==start)
            {
                if(a[i]<r)i++;
                otg+=st[i];
                num=0;
                if(a[i-1]<r)break;
            }
        }
    }
    return otg;
}
long long int delivery(int N, int K, int L, int p[])
{
    n=N;
    k=K;
    m=L;
    for(int i=0; i<n; i++)
    {
        a[i+1]=p[i];
    }
    l=(m-1)/2;
    r=(m+1)/2;
    prec();
    mi=go_from_mid();
    for(int i=0;i<k;i++)
    {
        mi=min(mi,go_from_left(i));
    }
    //cout<<mi<<endl;
    return mi;
}

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