Submission #832468

#	Time	Username	Problem	Language	Result	Execution time	Memory
832468		Valaki2	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	440 ms	200312 KiB

boxes

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

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int inf = 1e17 + 42;

int n, k, l;
int sz[2];
vector<int> pos[2];
vector<int> dp[2];

int ans;

long long delivery(signed N, signed K, signed L, signed p[]) {
    ans = inf;
    n = N, k = K, l = L;
    // EDGE CASE !!!!! van a 0-s helyen is
    int boundary = n;
    for(int i = 0; i < n; i++) {
        if(p[i] > l / 2) {
            boundary = i;
            break;
        }
    }
    pos[0].assign(1 + boundary, 0);
    pos[0][0] = 0;
    for(int i = 1; i <= boundary; i++) {
        pos[0][i] = p[i - 1];
    }

    pos[1].assign(1 + n - boundary, 0);
    pos[1][0] = 0;
    for(int i = 1; i <= n - boundary; i++) {
        pos[1][i] = l - p[n - i];
    }
    for(int j = 0; j < 2; j++) {
        sz[j] = pos[j].size() - 1;
        dp[j].assign(1 + sz[j], 0);
        for(int i = 1; i <= sz[j]; i++) {
            dp[j][i] = 2 * pos[j][i] + dp[j][max(0ll, i - k)];
        }
    }
    ans = min(ans, dp[0][sz[0]] + dp[1][sz[1]]);
    for(int i = 0; i <= sz[0]; i++) {
        if(i + k + sz[1] < n) {
            continue;
        }
        int j = max(0ll, n - i - k);
        ans = min(ans, dp[0][i] + l + dp[1][j]);
    }
    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