Submission #511055

#	Time	Username	Problem	Language	Result	Execution time	Memory
511055		Gurban	Boxes with souvenirs (IOI15_boxes)	C++17	25 / 100	1 ms	288 KiB

boxes

#include "bits/stdc++.h"
#include "boxes.h"
using namespace std;

using ll = long long;

ll delivery(int N, int K, int L, int p[]) {
    vector<int>cep,sag;
    int bnd = (L + 1) / 2;
    for(int i = 0;i < N;i++){
        if(p[i] <= bnd) cep.push_back(p[i]);
        else sag.push_back(L - p[i]);
    }
    reverse(sag.begin(),sag.end());
    vector<ll>cp_dp((int)cep.size());
    vector<ll>sg_dp((int)sag.size());
    
    int SZc = (int)cep.size();
    int SZs = (int)sag.size();

    for(int i = 0;i < SZc;i++){
        if(i < K) cp_dp[i] = 2ll*cep[i];
        else cp_dp[i] = 2ll*cep[i] + cp_dp[i - K];
    }
    for(int i = 0;i < SZs;i++){
        if(i < K) sg_dp[i] = 2ll*sag[i];
        else sg_dp[i] = 2ll*sag[i] + sg_dp[i - K];
    }

    ll ans = 0;
    if(!cep.empty()) ans += cp_dp.back();
    if(!sag.empty()) ans += sg_dp.back();

    // cout<<cp_dp.back()<<' '<<sg_dp.back()<<'\n';

    // return ans;

    for(int i = 0;i <= min(K,SZc);i++){
        ll nw = 0;
        if(i != SZc) nw = cp_dp[SZc - i - 1];
        
        ll now = nw;
        int lft = K - i;
        if(lft < SZs) now += sg_dp[SZs - lft - 1]; 
        
        ans = min(ans,now + L);
        
        lft = 2*K - i;
        if(lft < SZs) nw += sg_dp[SZs - lft - 1];
        
        ans = min(ans,nw + 2ll*L);
    }
    return ans;
}

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