Submission #320369

#	Time	Username	Problem	Language	Result	Execution time	Memory
320369		nikatamliani	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	535 ms	196656 KiB

boxes

#include <bits/stdc++.h>
#include "boxes.h"
using namespace std;
long long delivery(int N, int K, int L, int positions[]) {
    long long p[N], s[N];
    for(int i = 0; i < N; ++i) {
        p[i] = 2 * positions[i];
        if(i >= K) {
            p[i] += p[i - K];
        } 
    }
    for(int i = N - 1; i >= 0; --i) {
        s[i] = 2 * (L - positions[i]);
        if(i + K < N) {
            s[i] += s[i + K]; 
        }
    }
    long long answer = min(p[N - 1], s[0]);
    for(int i = 0; i < N - 1; ++i) {
        answer = min(answer, p[i] + s[i + 1]);
    }
    for(int start = 0; start + K - 1 < N; ++start) {
        int end = start + K - 1;
        long long left = (start > 0 ? p[start - 1] : 0);
        long long right = (end < N - 1 ? s[end + 1] : 0);
        long long middle = L;
        answer = min(answer, left + middle + right);
    }
    return answer;
}
// int main() {
//     int pos[] = {1, 2, 5};
//     cout << delivery(3, 2, 8, pos) << '\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