Submission #410003

#	Time	Username	Problem	Language	Result	Execution time	Memory
410003		robs	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	7 ms	396 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, dp1[maxn], dp2[maxn], ini[maxn], fim[maxn], resp;

int solve1(int i)
{
	if(i < 1)	return ini[1];
	if(dp1[i] != -INF)	return dp1[i];
	dp1[i] = solve1(i-k) + ini[i];
	return dp1[i];
}

int solve2(int j)
{
	if(j >= n)	return fim[n];
	if(dp2[j] != -INF)	return dp2[j];
	dp2[j] = solve2(j+k) + fim[j];
	return dp2[j];
}

long long delivery(int N, int K, int L, int p[])
{
	n = N; k = K;
	for(int x = 1; x <= n; x++)
	{
		dp1[x] = -INF;
		dp2[x] = -INF;
		ini[x] = 2*p[x];
		fim[x] = 2*(n-p[x]);
	}
	solve1(n);
	solve2(1);
	resp = 0;
	for(int x = 1; x <= n; x++)
		resp = max(resp, dp1[x]+dp2[x+1]);
	for(int x = 1; x <= n; x++)
		resp = max(resp, dp1[x]+k+dp2[x+k+1]);
	debug("dp1[]:\n");
	for(int x = 1; x <= n; x++)
		debug("%d ",dp1[x]);
	debug("\n");
	debug("dp2[]:\n");
	for(int x = 1; x <= n; x++)
		debug("%d ",dp2[x]);
	debug("\n");
	debug("0 voltas:\n");
	for(int x = 1; x <= n; x++)
		debug("%d ",min(resp, dp1[x]+dp2[x+1]));
	debug("\n");
	debug("1 voltas:\n");
	for(int x = 1; x <= n; x++)
		debug("%d ",min(resp, dp1[x]+k+dp2[x+k]));
	debug("\n");
	return resp;
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:24:38: warning: unused parameter 'L' [-Wunused-parameter]
   24 | long long delivery(int N, int K, int L, int p[])
      |                                  ~~~~^

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