Submission #1075535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075535		Elias	Boxes with souvenirs (IOI15_boxes)	C++17	100 / 100	759 ms	377020 KiB

boxes

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#endif

#include <bits/stdc++.h>

using namespace std;

#ifndef _DEBUG
#include "boxes.h"
#else
long long delivery(int N, int K, int L, int p[]);

#endif

#define ll long long

ll inf = LLONG_MAX / 10;

struct SegTree
{
	vector<ll> b;
	vector<ll> a;

	SegTree(int n)
	{
		b.resize(4 * n, inf);
		a.resize(n, inf);
	}

	ll segGet(int l, int r, int i, int ql, int qr)
	{
		if (qr <= l || r <= ql)
			return inf;
		if (ql <= l && qr >= r)
			return b[i];
		int m = (l + r) / 2;
		return min(segGet(l, m, i * 2 + 1, ql, qr), segGet(m, r, i * 2 + 2, ql, qr));
	}

	ll segSet(int l, int r, int i, int k, ll x)
	{
		if (r <= k || l > k)
			return b[i];
		if (l + 1 == r)
			return a[l] = b[i] = x;
		int m = (l + r) / 2;
		return b[i] = min(segSet(l, m, i * 2 + 1, k, x), segSet(m, r, i * 2 + 2, k, x));
	}
};

vector<ll> calculate_pref(int l, vector<int> a, int k)
{
	int n = a.size() + 1;

	vector<ll> out(n);

	deque<pair<ll, int>> sliding_window;
	sliding_window.push_back({0, 0});

	for (int i = 1; i < n; i++)
	{
		ll prev = 0;
		while (sliding_window.size() > 0 && i - sliding_window.front().second > k)
			sliding_window.pop_front();

		if (sliding_window.size())
			prev = sliding_window.front().first;

		ll cost = int64_t(a[i - 1]) + prev + min<ll>(a[i - 1], l - a[i - 1]);

		out[i] = cost;
		while (sliding_window.size() > 0 && sliding_window.back().first >= cost)
			sliding_window.pop_back();
		sliding_window.push_back({cost, i});
	}

	return out;
}

long long delivery(int N, int K, int L, int p[])
{
	vector<int> positions(N);

	for (int i = 0; i < N; i++)
		positions[i] = p[i];

	vector<ll> pref = calculate_pref(L, positions, K);
	reverse(positions.begin(), positions.end());
	for (int i = 0; i < N; i++)
		positions[i] = L - positions[i];
	vector<ll> suff = calculate_pref(L, positions, K);

	ll best = inf;

	for (int cnt_a = 0; cnt_a <= N; cnt_a++)
	{
		int cnt_b = N - cnt_a;

		best = min(best, pref[cnt_a] + suff[cnt_b]);
	}

	return best;
}

#ifdef _DEBUG

#include <stdio.h>
#include <stdlib.h>

static char buffer[1024];
static int currentChar = 0;
static int charsNumber = 0;

static inline int read()
{
	if (charsNumber < 0)
	{
		exit(1);
	}
	if (!charsNumber || currentChar == charsNumber)
	{
		charsNumber = (int)fread(buffer, sizeof(buffer[0]), sizeof(buffer), stdin);
		currentChar = 0;
	}
	if (charsNumber <= 0)
	{
		return -1;
	}
	return buffer[currentChar++];
}

static inline int readInt()
{
	int x;
	cin >> x;
	return x;
}

int main()
{
	int N, K, L, i;
	N = readInt();
	K = readInt();
	L = readInt();

	int *p = (int *)malloc(sizeof(int) * (unsigned int)N);

	for (i = 0; i < N; i++)
	{
		p[i] = readInt();
	}

	fprintf(stdout, "%lld\n", delivery(N, K, L, p));
	return 0;
}

#endif

Compilation message (stderr)

boxes.cpp: In function 'std::vector<long long int> calculate_pref(int, std::vector<int>, int)':
boxes.cpp:56:19: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   56 |  int n = a.size() + 1;
      |          ~~~~~~~~~^~~

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