Submission #410025

#	Time	Username	Problem	Language	Result	Execution time	Memory
410025		robs	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	1 ms	332 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
#define debug(args...) fprintf(stderr, args)
using namespace std;
const int maxn = 2e7, INF = 1e9;
int n, k, m, dp1[maxn], dp2[maxn], ini[maxn], fim[maxn], resp;

long long delivery(int N, int K, int L, int p[])
{
	n = N; m = L; k = K; resp = INF;
	
	for(int x = 0; x < n; x++)
		ini[x] = 2*p[x] + ((x >= k)?ini[x-k]:0);
	for(int x = n-1; x >= 0; x--)
		fim[x] = 2*(m-p[x]) + ((x+k < n)?ini[x+k]:0);
	
	for(int x = 0; x < n-1; x++)
		resp = min(resp, ini[x]+fim[x+1]);
	for(int x = 1; x+k < n; x++)
		resp = min(resp, ini[x-1]+m+fim[x+k]);
	if(k == n)	resp = min(resp, m);
	else	resp = min(resp, min(fim[k]+m, m+ini[n-k+1]));
	
	debug("%d\n",resp);
	return resp;
}

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