Submission #1229640

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229640		boris_mihov	Nile (IOI24_nile)	C++20	67 / 100	2095 ms	4948 KiB

nile

#include "nile.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXN = 100000 + 10;
const llong INF = 1e18;

int n;
struct Delivery
{
	int a, b, w;
	friend bool operator < (const Delivery &a, const Delivery &b)
	{
		return a.w < b.w;
	}
};

Delivery s[MAXN];

llong rangeQuery(int l, int r, int d)
{
	llong sum = 0;
	for (int i = l ; i <= r ; ++i)
	{
		sum += s[i].b;
	}

	if ((r - l + 1) % 2 == 0)
	{
		return sum;
	}

	llong ans = INF;
	for (int i = l ; i <= r ; i += 2)
	{
		ans = std::min(ans, sum - s[i].b + s[i].a);
	}

	for (int i = l + 1 ; i <= r ; i += 2)
	{
		if (s[i + 1].w - s[i - 1].w <= d)
		{
			ans = std::min(ans, sum - s[i].b + s[i].a);
		}
	}

	return ans;
}

llong query(int d)
{
	int last = 1;
	llong answer = 0;
	for (int i = 2 ; i <= n ; ++i)
	{
		if (s[i].w - s[i - 1].w > d)
		{
			answer += rangeQuery(last, i - 1, d);
			last = i;
		}
	}

	answer += rangeQuery(last, n, d);
	return answer;
}

std::vector<long long> calculate_costs(std::vector <int> W, std::vector <int> A, std::vector <int> B, std::vector <int> E)
{
	n = W.size();
	for (int i = 1 ; i <= n ; ++i)
	{
		s[i].w = W[i - 1];
		s[i].a = A[i - 1];
		s[i].b = B[i - 1];
	}

	std::sort(s + 1, s + 1 + n);
	std::vector <llong> sol;
	for (const int &d : E)
	{
		sol.push_back(query(d));
	}

	return sol;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18