Submission #117494

#	Time	Username	Problem	Language	Result	Execution time	Memory
117494		zubec	Boxes with souvenirs (IOI15_boxes)	C++14	50 / 100	2044 ms	15656 KiB

boxes

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

long long dp[1000100];

long long delivery(int N, int K, int L, int p[]) {

    int mid = L/2;
    for (int i = 1; i <= N; i++){
        dp[i] = 1e18;
        bool bb = 0;
        int pos = p[i-1];
        for (int j = 1; j <= K; j++){
            if (i-j < 0)
                break;
            int pos2 = p[i-j];
            if (mid != pos2 && mid != pos && (mid-pos2)/abs(mid-pos2) != (mid-pos)/abs(mid-pos) ){
                bb = 1;
            }
            if (bb){
                dp[i] = min(dp[i], dp[i-j] + L);
            } else {
                dp[i] = min(dp[i], dp[i-j] + max(min(pos2, L-pos2), min(pos, L-pos))*2);
            }
        }
    }
    return dp[N];

}

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