Submission #427777

#	Time	Username	Problem	Language	Result	Execution time	Memory
427777		illyakr	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	625 ms	372076 KiB

boxes

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

ll dpFOR[10000002];
ll dpBACK[10000002];
ll a[10000002];
ll res = 1010101010;
long long delivery(int N, int K, int L, int p[]) {
    for (int i = 1; i <= N; i++)
        a[i] = p[i - 1];

    for (int i = 1; i <= N; i++) {
        if (i <= K)dpFOR[i] = a[i] + min(a[i], L - a[i]);
        else dpFOR[i] = dpFOR[i - K] + a[i] + min(a[i], L - a[i]);
    }
    for (int i = N; i >= 1; i--) {
        if (N - i + 1 <= K)dpBACK[i] = (L - a[i]) + min(a[i], L - a[i]);
        else dpBACK[i] = dpBACK[i + K] + (L - a[i]) + min(a[i], L - a[i]);
    }
//    for (int i = 1; i <= N; i++) {
//        cout << dpFOR[i] << " ";
//    }
//    cout << endl;
//    for (int i = 1; i <= N; i++) {
//        cout << dpBACK[i] << " ";
//    }
//    cout << endl;
    res = min(dpFOR[N], dpBACK[1]);
    for (int i = 1; i < N; i++) {
        res = min(res, dpFOR[i] + dpBACK[i + 1]);
    }
    return res;
}
/**
3 2 8
1 2 5

*/

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