Submission #231662

#	Time	Username	Problem	Language	Result	Execution time	Memory
231662		crimsonred	Solar Storm (NOI20_solarstorm)	C++17	100 / 100	516 ms	193160 KiB

SolarStorm

#include <bits/stdc++.h>
using namespace std;

#define mod 1'000'000'007
typedef long long ll;

template<typename T>
void deb(initializer_list<T> l)
{
	for (auto &e : l)
		cout << e << ' ';
	cout << endl;
}

ll n, s, k;
vector<ll> coord, a, parents, leftx, rightx, pref;
vector<vector<ll>> adj;
ll mx = 0;
pair<ll, ll> ans;

void dfs(ll u, ll parent, vector<ll>& stk)
{
	stk.push_back(u);
	for (auto &v : adj[u])
		if (v != parent)
			dfs(v, u, stk);

	ll ancestor = stk.size() >= s ? stk[stk.size() - s] : stk[0];
	// [u, ancestor]
	ll sum = pref[rightx[ancestor]] - (leftx[u] ? pref[leftx[u] - 1] : 0);
	if (sum > mx)
	{
		mx = sum;
		ans = {u, ancestor};
	}

	stk.pop_back();
}

void solve()
{
	cin >> n >> s >> k;
	coord.resize(n);
	a.resize(n);
	leftx.resize(n);
	rightx.resize(n);
	parents.reserve(n);
	adj.resize(n);
	pref.resize(n);

	coord[0] = 0;
	for (ll i = 1; i < n; ++i)
	{
		ll diff;
		cin >> diff;
		coord[i] = coord[i - 1] + diff;
	}

	for (auto &e : a)
		cin >> e;

	leftx[0] = 0;
	rightx[0] = 0;
	// shield range: [leftx[i], rightx[i]]
	ll leftptr = 0;
	ll rightptr = 0;
	for (ll i = 0; i < n; ++i)
	{
		while (rightptr < n && coord[rightptr] - coord[i] <= k)
			++rightptr;
		--rightptr;

		while (coord[i] - coord[leftptr] > k)
			++leftptr;

		leftx[i] = leftptr;
		rightx[i] = rightptr;
	}

	pref[0] = a[0];
	for (ll i = 1; i < n; ++i)
		pref[i] = a[i] + pref[i - 1];

	for (ll i = 0; i < n; ++i)
	{
		ll nextnode = rightx[i];
		if (nextnode + 1 < n)
			++nextnode;
		nextnode = rightx[nextnode];
		if (coord[nextnode] - coord[i] > k)
		{
			adj[i].push_back(nextnode);
			adj[nextnode].push_back(i);
		}
		else
			parents.push_back(i);
	}

	vector<ll> stk;
	stk.reserve(n);
	for (auto &e : parents)
		dfs(e, -1, stk);

	auto [first, last] = ans;
	vector<ll> shields;
	shields.reserve(n);
	shields.push_back(first + 1);
	while (first != last)
	{
		for (auto &v : adj[first])
		{
			if (v > first)
			{
				shields.push_back(v + 1);
				first = v;
				break;
			}
		}
	}

	cout << shields.size() << '\n';
	for (auto &e : shields)
		cout << e << ' ';
	cout << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int t = 1;
	// cin >> t;
	while (t--)
		solve();

	return 0;
}

Compilation message (stderr)

SolarStorm.cpp: In function 'void dfs(ll, ll, std::vector<long long int>&)':
SolarStorm.cpp:28:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  ll ancestor = stk.size() >= s ? stk[stk.size() - s] : stk[0];
                ~~~~~~~~~~~^~~~

• Subtask 1: 10 / 10
• Subtask 2: 7 / 7
• Subtask 3: 11 / 11
• Subtask 4: 8 / 8
• Subtask 5: 18 / 18
• Subtask 6: 16 / 16
• Subtask 7: 30 / 30