Submission #927951

#	Time	Username	Problem	Language	Result	Execution time	Memory
927951		TAhmed33	Boxes with souvenirs (IOI15_boxes)	C++98	100 / 100	1526 ms	326516 KiB

boxes

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("trapv")
typedef long long ll;
struct Mono {
	stack <pair <ll, ll>> s1, s2;
	int sze = 0;
	ll get_min () {
		if (s1.empty() || s2.empty()) {
			return s1.empty() ? s2.top().second : s1.top().second;
		} else {
			return min(s1.top().second, s2.top().second);
		}
	}
	void insert (ll x) {
		ll mn = s1.empty() ? x : min(x, s1.top().second);
		s1.push({x, mn});
		sze++;
	}
	void remove () {
		if (s2.empty()) while (!s1.empty()) {
			ll x = s1.top().first; s1.pop();
			ll mn = (s2.empty() ? x : min(x, s2.top().second));
			s2.push({x, mn});
		}
		sze--;
		s2.pop();
	}
};
Mono cur1, cur2;
ll n, k, l;
ll arr[10000001];
ll dp[10000001];
inline ll mindist (int a, int b) {
	return min({2 * arr[b], 2 * (l - arr[a]), l});
}
long long delivery (int a, int b, int c, int pp[]) {
	n = a; k = b; l = c;
	for (int i = 0; i < n; i++) {
		arr[i + 1] = pp[i];
	}
	dp[n + 1] = 0;
	cur1.insert(0);
	cur2.insert(2 * arr[n]);
	for (int i = n; i >= 1; i--) {
		if (cur1.sze > k) {
			cur1.remove();
			cur2.remove();
		}
		dp[i] = min({
			cur1.get_min() + l,
			cur1.get_min() + 2 * (l - arr[i]),
			cur2.get_min()
		});
		if (i == 1) break;
		cur1.insert(dp[i]);
		cur2.insert(dp[i] + 2 * arr[i - 1]);
	}
	return dp[1];
}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:45:15: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   45 |  for (int i = n; i >= 1; i--) {
      |               ^

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