Submission #1192569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192569		Joon_Yorigami	Boxes with souvenirs (IOI15_boxes)	C++20	35 / 100	0 ms	328 KiB

boxes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll delivery(int n, int k, int l, int* positions)
{
    vector<pair<ll,ll>> left;
    vector<pair<ll,ll>> right;
    map<ll,ll> memo;
    ll num;
    for(int i=0;i<n;i++)
    {
        num=positions[i];
        if(memo.find(num)==memo.end())
        {
            memo[num]=1;
        }
        else
        {
            memo[num]+=1;
        }
    }
    for(auto p:memo)
    {
        if(p.first<=l/2)
        {
            left.push_back(p);
        }
        else
        {
            right.push_back(p);
        }
    }
    ll leftoverright,leftoverleft,ans;
    ans=0;
    leftoverright=0;
    leftoverleft=0;
    reverse(right.begin(),right.end());
    for(int i=left.size()-1;i>=0;i--)
    {
        if(leftoverleft>0)
        {
            left[i].second-=leftoverleft;
            leftoverleft=0;
        }
        if(left[i].second<0)
        {
            leftoverleft=abs(left[i].second);
            continue;
        }
        ans+=(left[i].second+k-1)/k*2*left[i].first;
        leftoverleft=0;
        if(left[i].second%k>0)
        {
            leftoverleft=k-(left[i].second%k);
        }
    }
    for(int i=right.size()-1;i>=0;i--)
    {
        if(leftoverright>0)
        {
            right[i].second-=leftoverright;
            leftoverright=0;
        }
        if(right[i].second<0)
        {
            leftoverright=abs(right[i].second);
            continue;
        }
        ans+=(right[i].second+k-1)/k*2*(l-right[i].first);
        leftoverright=0;
        if(right[i].second%k>0)
        {
            leftoverright=k-(right[i].second%k);
        }
    }
    if(right.size()>0 && left.size()>0 && leftoverleft>0 && leftoverright>0 && leftoverleft>=(k-leftoverright) && l<left.back().first*2+(l-right.back().first)*2)
    {
        ans-=left.back().first*2+(l-right.back().first)*2;
        ans+=l;
    }
    return ans;
}
/*
int main()
{
    int n,k,l,owo;
    int positions[10000];
    cin >> n >> k >> l;
    for(int i=0;i<n;i++)
    {
        cin >> owo;
        positions[i]=owo;
    }
    cout << delivery(n,k,l,positions) << endl;
}
*/

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