Submission #1152992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1152992		vladilius	Boxes with souvenirs (IOI15_boxes)	C++20	100 / 100	514 ms	161004 KiB

boxes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e18;

ll delivery(int n, int k, int L, int X[]){
    vector<int> x(n + 1);
    for (int i = 1; i <= n; i++) x[i] = X[i - 1];
    sort(x.begin() + 1, x.end());
    vector<ll> dp(n + 1, inf); dp[0] = 0;
    
    auto f = [&](int i){
        return dp[i - 1] + 2 * (L - x[i]);
    };
    
    deque<int> q; q.pb(1);
    for (int i = 1; i <= n; i++){
        int l = max(1, i - k + 1);
        while (!q.empty() && q.front() < l) q.pop_front();
        dp[i] = min({dp[l - 1] + L, dp[l - 1] + 2 * x[i], f(q.front())});
        
        if (i == n) break;
        ll F = f(i + 1);
        while (!q.empty() && f(q.back()) >= F){
            q.pop_back();
        }
        q.pb(i + 1);
    }
    return dp[n];
}

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