Submission #221803

#	Time	Username	Problem	Language	Result	Execution time	Memory
221803		patrikpavic2	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	570 ms	278520 KiB

boxes

/**
* user:  ppavic
* fname: Patrik
* lname: Pavić
* task:  boxes
* score: 100.0
* date:  2019-06-21 08:46:28.793839
*/
#include "boxes.h"
#include <algorithm>
#include <cstdio>

using namespace std;

typedef long long ll;

const int N = 1e7 + 500;

ll prf[N], suf[N];

ll delivery(int n, int K, int L, int p[]) {
    for(int i = 0;i < n;i++){
  		prf[i] = p[i] +  min(L - p[i], p[i]);
  		if(i >= K) prf[i] += prf[i - K];  	
    }
    for(int i = n - 1;i >= 0;i--){
  		suf[i] = L - p[i] +  min(L - p[i], p[i]);
    	if(i + K < n) suf[i] += suf[i + K];
    } suf[n] = 0;
    ll sol = suf[0];
    for(int i = 0;i < n	;i++){
    	sol = min(sol, prf[i] + suf[i + 1]);
    	//printf("%d %d\n", prf[i], suf[i + 1]);
    }
    return sol;
}

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