Submission #880026

#	Time	Username	Problem	Language	Result	Execution time	Memory
880026		JakobZorz	Boxes with souvenirs (IOI15_boxes)	C++14	25 / 100	1 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-l]+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-l]+2*pos2[j];
    }
    
    ll res=cost1.back()+cost2.back();
    /*for(int i1=0;i1<(int)cost1.size();i1++){
        int start=(cost1.size()+cost2.size()-2-i1)%l;
        
        for(int i2=start;i2<(int)cost2.size();i2+=l){
            ll rem=cost1.size()+cost2.size()-2-i1-i2;
            ll curr=cost1[i1]+cost2[i2]+rem/l*n;
            //cout<<curr<<" "<<i1<<" "<<i2<<" "<<rem<<"\n";
            res=min(res,curr);
        }
    }*/
    
    for(int i=0;i<=l;i++){
        int i1=(int)cost1.size()-1-i;
        int i2=(int)cost2.size()-1-l-i;
        
        ll curr=cost1[i1]+cost2[i2]+n;
        res=min(res,curr);
    }
    
    return res;
}

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