Submission #1151409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151409		AlgorithmWarrior	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	412 ms	196376 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
#include <stdio.h>
#include <stdlib.h>

using namespace std;

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

void rev(int v[],int n){
    int i;
    for(i=0;i<n-i-1;++i)
        swap(v[i],v[n-i-1]);
}

long long delivery(int N, int K, int L, int p[]) {
    vector<long long>dp1(N),dp2(N);
    int i;
    for(i=0;i<N;++i)
        dp1[i]=1LL*p[i]+1LL*min(p[i],L-p[i])+((i>=K)?dp1[i-K]:0);
    rev(p,N);
    for(i=0;i<N;++i){
        p[i]=L-p[i];
        dp2[i]=1LL*p[i]+1LL*min(p[i],L-p[i])+((i>=K)?dp2[i-K]:0);
    }
    long long ans=min(dp1[N-1],dp2[N-1]);
    for(i=0;i<N-1;++i)
        minself(ans,dp1[i]+dp2[N-2-i]);
    return ans;
}

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