Submission #1034106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034106		Zicrus	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	331 ms	524288 KiB

boxes

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

typedef long long ll;

ll sub1(int n, int k, int l, vector<ll> p) {
    ll sum = 0;
    for (auto &e : p) sum += 2*min(e, l-e);
    return sum;
}

ll sub2(int n, int k, int l, vector<ll> p) {
    ll fR = lower_bound(p.begin(), p.end(), l/2) - p.begin();
    if (fR == 0) return 2*(l-p[fR]);
    ll fL = fR-1;
    if (fL == n-1) return 2*p[fL];
    return p[fL] + l-p[fR] + min(p[fR]-p[fL], l-(p[fR]-p[fL]));
}

ll delivery(int n, int k, int l, int p11[]) {
    vector<ll> p(n);
    for (int i = 0; i < n; i++) p[i] = p11[i];
    //if (k == 1) return sub1(n, k, l, p);
    //if (k == n) return sub2(n, k, l, p);

    vector<vector<ll>> dp(n, vector<ll>(k, 1ll << 62ll));
    dp[0][k-1] = min(p[0], l-p[0]);
    for (int i = 1; i < n; i++) {
        dp[i][k-1] = dp[i-1][k-1];
        for (int j = 0; j < k-1; j++) {
            dp[i][j] = min(p[i]-p[i-1], l-(p[i]-p[i-1])) + dp[i-1][j+1];
            //
            dp[i][k-1] = min(dp[i][k-1], dp[i-1][j]);
        }
        dp[i][k-1] += min(p[i-1], l-p[i-1]) + min(p[i], l-p[i]);
    }

    ll res = dp[n-1][0];
    for (int j = 1; j < k; j++) {
        res = min(res, dp[n-1][j]);
    }
    res += min(p[n-1], l-p[n-1]);

    return res;
}

Compilation message (stderr)

boxes.cpp: In function 'll sub1(int, int, int, std::vector<long long int>)':
boxes.cpp:7:13: warning: unused parameter 'n' [-Wunused-parameter]
    7 | ll sub1(int n, int k, int l, vector<ll> p) {
      |         ~~~~^
boxes.cpp:7:20: warning: unused parameter 'k' [-Wunused-parameter]
    7 | ll sub1(int n, int k, int l, vector<ll> p) {
      |                ~~~~^
boxes.cpp: In function 'll sub2(int, int, int, std::vector<long long int>)':
boxes.cpp:13:20: warning: unused parameter 'k' [-Wunused-parameter]
   13 | ll sub2(int n, int k, int l, vector<ll> p) {
      |                ~~~~^

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