Submission #314147

#	Time	Username	Problem	Language	Result	Execution time	Memory
314147		joseacaz	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	570 ms	246392 KiB

boxes

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

using namespace std;
typedef long long ll;
typedef vector<int> vi;

const int MAXN = 1e7 + 5;
int N, K, L;
ll pre[MAXN], suf[MAXN];

ll delivery(int _n, int _k, int _l, int p[])
{
	N = _n, K = _k, L = _l;
    for(int i = 0; i < N; i++)
        pre[i] = (i - K >= 0 ? pre[i - K] : 0) + 2*p[i];
    for(int i = N - 1; i >= 0; i--)
        suf[i] = (i + K < N ? suf[i + K] : 0) + 2*(L-p[i]);
    
    ll ans = min(pre[N - 1], suf[0]);
    for(int i = 0; i < N - 1; i++)
        ans = min(ans, pre[i] + suf[i + 1]);
    ans = min(ans, L + suf[K]);
    ans = min(ans, pre[N - K - 1] + L);
    for(int i = 0; i < N - K - 1; i++)
        ans = min(ans, pre[i] + suf[i + K + 1] + L);
    
    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