Submission #550443

#	Time	Username	Problem	Language	Result	Execution time	Memory
550443		elazarkoren	Boxes with souvenirs (IOI15_boxes)	C++17	10 / 100	387 ms	340 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int MAX_N = 1e6 + 5;
const ll infinity = 1e18;

//ll dp[MAX_N];

//ll Solve(vi &p, int l) {
//    int n = p.size();
//    ll ans = l;
//    sort(all(p));
//    for (int i = 0; i < n - 1; i++) {
//        chkmin(ans, ll(2) * (p[i] + (l - p[i + 1])));
//    }
//    chkmin(ans, ll(2) * p[n - 1]);
//    chkmin(ans, ll(2) * (l - p[0]));
//    return ans;
//}

int n, k, l;

ll dp[MAX_N];

ll Solve(int ind, vi &p) {
    ll ans = 0;
    for (int i = 0; i < ind; i++) {
        dp[i] = (i > 0 ? dp[i - 1] : 0);
        int m = max(0, i - k);
        for (int j = i - 1; j >= m; j--) {
            chkmin(dp[i], dp[j]);
        }
        dp[i] += min<ll>(l, 2 * p[i]);
//        int r = min(i + k, ind);
//        ans += min<ll>(l, 2 * p[r - 1]);
    }
    for (int i = n - 1; i >= ind; i--) {
        dp[i] = dp[i + 1];
        int m = min(n, i + k);
        for (int j = i + 1; j <= m; j++) {
            chkmin(dp[i], dp[j]);
        }
        dp[i] += min<ll>(l, 2 * (l - p[i]));
//        int left = max(ind, i - k + 1);
//        ans += min<ll>(l, 2 * (l - p[left]));
    }
    return (ind > 0 ? dp[ind - 1] : 0) + dp[ind];
}

long long delivery(int N, int K, int L, int P[]) {
    n = N, k = K, l = L;
    vi p(n);
    ll ans = infinity;
    for (int i = 0; i < n; i++) p[i] = P[i];
    for (int ind = 0; ind <= n; ind++) {
        chkmin(ans, Solve(ind, p));
    }
//    sort(p, p + n);
//    for (int i = 0; i < n; i++) {
//        vi curr;
//        dp[i] = infinity;
//        for (int j = i; j >= 0; j--) {
//            curr.push_back(p[j]);
//            if (curr.size() > k) break;
//            ll x = (j > 0 ? dp[j - 1] : 0);
//            chkmin(dp[i], x + Solve(curr, l));
//        }
//    }
//    chkmin(ans, dp[n - 1]);
    return ans;
}
//3 2 8
//1 2 5

Compilation message (stderr)

boxes.cpp: In function 'll Solve(int, vi&)':
boxes.cpp:37:8: warning: unused variable 'ans' [-Wunused-variable]
   37 |     ll ans = 0;
      |        ^~~

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