Submission #880010

#	Time	Username	Problem	Language	Result	Execution time	Memory
880010		JakobZorz	Boxes with souvenirs (IOI15_boxes)	C++14	10 / 100	2 ms	348 KiB

boxes

#include"boxes.h"
#include<vector>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;

ll delivery(int k,int l,int n,int p[]){
    vector<int>pos1,pos2;
    pos1.push_back(0);
    pos2.push_back(0);
    for(int i=0;i<k;i++){
        if(p[i]<=n/2)
            pos1.push_back(p[i]);
    }
    
    for(int i=k-1;i>=0;i--){
        if(p[i]>n/2)
            pos2.push_back(n-p[i]);
    }
    
    vector<ll>cost1(pos1.size()),cost2(pos2.size());
    for(int i=0;i<min((int)cost1.size(),l);i++){
        cost1[i]=2*pos1[i];
        for(int j=i+l;j<(int)cost1.size();j+=l)
            cost1[j]=cost1[j-i]+2*pos1[j];
    }
    
    for(int i=0;i<min((int)cost2.size(),l);i++){
        cost2[i]=2*pos2[i];
        for(int j=i+l;j<(int)cost2.size();j+=l)
            cost2[j]=cost2[j-i]+2*pos2[j];
    }
    
    ll res=1e18;
    for(int i1=0;i1<(int)cost1.size();i1++){
        for(int i2=0;i2<(int)cost2.size();i2++){
            ll rem=cost1.size()+cost2.size()-2-i1-i2;
            ll curr=cost1[i1]+cost2[i2]+(rem+l-1)/l*n;
            //cout<<curr<<" "<<i1<<" "<<i2<<" "<<rem<<"\n";
            res=min(res,curr);
        }
    }
    
    return res;
}

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