Submission #364626

#	Time	Username	Problem	Language	Result	Execution time	Memory
364626		BartolM	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	565 ms	260784 KiB

boxes

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

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const int N=1e7+5;
const ll MAX=(ll)INF*INF;

int p[N];
ll pref[N], suff[N];

ll delivery(int n, int k, int l, int poc[]) {
    for (int i=0; i<n; ++i) p[i+1]=poc[i];
    pref[0]=0;
    for (int i=1; i<=n; ++i) {
        int dod=min(l, 2*p[i]);
        pref[i]=pref[max(0, i-k)]+dod;
    }
    suff[n+1]=0;
    for (int i=n; i>=1; --i) {
        int dod=min(l, 2*(l-p[i]));
        suff[i]=suff[min(n+1, i+k)]+dod;
    }

    ll sol=min(pref[n], suff[1]);
    for (int i=1; i<=n; ++i) sol=min(sol, pref[i]+suff[i+1]);

    return sol;
}

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