Submission #780172

#	Time	Username	Problem	Language	Result	Execution time	Memory
780172		vjudge1	선물상자 (IOI15_boxes)	C++17	70 / 100	2024 ms	222932 KiB

boxes

#include "boxes.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<long long, long long>
#define st first
#define nd second
#define sp " "
#define endl "\n"
#define ll long long


const ll INF = 2e18 + 7;

long long delivery(int N, int K, int L, int p[]) {
    int n = N, k = K, l = L;
    sort(p, p + n);
    int pos = 0;
    while(pos< n && p[pos] <= L / 2) pos++;

    vector<ll> dp(n + 5, INF);
    multiset<ll> fw, bk;

    dp[n] = 0;
    for (int i = n - 1; i >= 0; i--){
        if (i + k < n){
            if (p[i + k] >= L / 2){
                fw.erase(fw.find(dp[i + k + 1]));
            }
            if (p[i + k] <= L / 2){
                bk.erase(bk.find(dp[i + k + 1] + 2 * p[i + k]));
            }
        }

        if (p[i] <= L / 2){
            bk.insert(dp[i + 1] + 2 * p[i]);
        }
        if (p[i] >= L / 2){
            fw.insert(dp[i + 1]);
        }

        ll t1 = INF, t2 = INF;
        if (p[i] <= L / 2){
            if (!fw.empty()){
                t1 = *fw.begin() + L;
            }
            if (!bk.empty()){
                t2 = *bk.begin();
            }
        }
        else{
            if (!fw.empty()){
                t1 = *fw.begin() + 2 * (L - p[i]);
            }
        }
        dp[i] = min(t1, t2);
    }

    return dp[0];
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:16:23: warning: unused variable 'l' [-Wunused-variable]
   16 |     int n = N, k = K, l = L;
      |                       ^

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