Submission #1035345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035345		Zicrus	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	442 ms	215880 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
 
typedef long long ll;
 
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];

    ll sum = 0;
    ll pos = 0;
    for (int i = 0; i < n; i++) {
        sum += min(abs(p[i]-pos), l-abs(p[i]-pos));
        pos = p[i];
    }
    sum += min(pos, l-pos);

    ll res = 1ll << 62ll;
    for (int j = 0; j < k; j++) {
        ll val = sum;
        for (int i = j; i+1 < n; i += k) {
            val -= min(p[i+1]-p[i], l-(p[i+1]-p[i]));
            val += min(p[i], l-p[i]);
            val += min(p[i+1], l-p[i+1]);
        }
        res = min(res, val);
    }
 
    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