Submission #549384

#	Time	Username	Problem	Language	Result	Execution time	Memory
549384		joshjms	Boxes with souvenirs (IOI15_boxes)	C++14	0 / 100	4 ms	380 KiB

boxes

#include "boxes.h"

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

#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define debug(x) cout << #x << " => " << x << "\n";

const int mod = 1e9 + 7;

int n, k, l, p[10000005], idx;
int le, ri;

ll dp[10000005][2];
ll ans;

ll delivery(int N, int K, int L, int P[]) {
    n = N, k = K, l = L;
    for(int i = 0; i < n; i++) {
        if(P[i]) p[++idx] = P[i];
    }
    n = idx;
    if(n == 0) return 0;
    le = 0, ri = 1;
    for(; ri <= n; ri++) {
        while(ri - le > k && le < ri) 
            le++;
        assert(p[ri] >= 0 && p[ri] < l && p[le] >= 0 && p[le] < l);
        dp[p[ri]][0] = dp[p[le]][0] + min(l, p[ri] * 2);
    }
    reverse(p + 1, p + n + 1);
    le = 0, ri = 1;
    for(; ri <= n; ri++) {
        while(ri - le > k && le < ri)
            le++;
        assert(p[ri] >= 0 && p[ri] < l && p[le] >= 0 && p[le] < l);
        dp[p[ri]][1] = dp[p[le]][1] + min(l, ((l - p[ri]) % l) * 2);
    }
    // ans = min(dp[p[1]][0], dp[p[n]][1]);
    // for(int i = 2; i <= n; i++) {
    //     assert(p[i] >= 0 && p[i] < l && p[i - 1] >= 0 && p[i - 1] < l);
    //     ans = min(ans, dp[p[i]][0] + dp[p[i - 1]][1]);
    // }
    return ans;
}

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