Submission #1203396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203396		AMel0n	선물상자 (IOI15_boxes)	C++20	100 / 100	285 ms	117896 KiB

boxes

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

typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
// #define F first 
// #define S second

#include "boxes.h"

ll delivery(int N, int K, int L, int p[]) {
    // never optimal to take more than one full circle

    vector<ll> dp(N+1);
    ll mxL= 0, mxR = 0;
    ll i = 0;
    while((ll)p[i] <= L/2 && i < N) {
        if (i-K >= 0) dp[i] = dp[i-K] + 2ll*(ll)p[i];
        else dp[i] = 2ll*(ll)p[i];
        mxL = max(mxL, dp[i]);
        i++;
    }
    i = N-1;
    while((ll)p[i] > L/2 && i >= 0) {
        if (i+K < N) dp[i] = dp[i+K] + 2ll*((ll)L-(ll)p[i]);
        else dp[i] = 2ll*((ll)L-(ll)p[i]);
        mxR = max(mxR, dp[i]);
        i--;
    }

    ll res = mxL + mxR;
    if (p[K-1] > L/2) res = min(res, L+dp[K]);
    FOR(i, N) {
        if (i+K+1 <= N && p[i] <= L/2 && p[i+K] > L/2) res = min(res, L + dp[i] + dp[i+K+1]);
    }
    return res;
}

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