Submission #224550

#	Time	Username	Problem	Language	Result	Execution time	Memory
224550		Berted	Mountains (NOI20_mountains)	C++14	0 / 100	2083 ms	52600 KiB

Mountains

#include <iostream>
#include <vector>
#define vi vector<int>
#define fst first
#define snd second
#define pub push_back
#define ll long long
using namespace std;
const int MX = 1000001, LG = 20;
int s, n;
ll k, dst[MX] = {}, vpf[MX] = {}, sps[MX][LG] = {}, mx, rs, i1, i2, dst1, dst2;
vector<int> ans;
int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> s >> k;
	for (int i = 1; i < n; i++) {cin >> dst[i];}
	for (int i = 1; i <= n; i++) {cin >> vpf[i]; vpf[i] += vpf[i - 1];}
	//i1 = i2 = 1;
	for (int i = 0; i < n; i++)
	{
		if (i2 < i) {dst2 = dst1 = 0; i2 = i1 = i;}
		else if (i1 < i) {dst1 = 0; dst2 -= dst[i]; i1 = i;}
		else {dst1 -= dst[i];}
		for (; i1 < n - 1 && dst1 + dst[i1 + 1] <= k; i1++)
		{
			dst1 += dst[i1 + 1];
			if (i1 + 1 <= i2) {dst2 -= dst[i1 + 1];}
			else {i2++;}
		}
		for (; i2 < n - 1 && dst2 + dst[i2 + 1] <= k; i2++)
		{
			dst2 += dst[i2 + 1];
		}
		sps[i][0] = i2; 
		//cout << i1 << " " << i2 << "\n";
	}
	for (int i = 1; (1 << i) <= s; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (sps[j][i - 1] == n - 1) {sps[j][i] = n - 1;}
			else {sps[j][i] = sps[sps[j][i - 1] + 1][i - 1];}
		}
	}
	//cout << "----\n";
	for (int i = 0; i < n; i++)
	{
		int cr = i - 1;
		for (int j = 0; (1 << j) <= s; j++)
		{
			if ((1 << j) & s) 
			{
				if (cr < n - 1) {cr = sps[cr + 1][j];}		
			}
		}
		//cout << i << " " << cr << "\n";
		if (vpf[cr + 1] - vpf[i] > mx)
		{
			mx = vpf[cr + 1] - vpf[i];
			rs = i;
		}
	}
	//cout << mx << "\n";
	i1 = rs, i2 = rs, dst1 = 0, dst2 = 0;
	while (ans.size() < s && rs < n)
	{
		for (; i1 < n - 1 && dst1 + dst[i1 + 1] <= k; i1++)
		{
			dst1 += dst[i1 + 1];
			if (i1 + 1 <= i2) {dst2 -= dst[i1 + 1];}
			else {i2++;}
		}
		for (; i2 < n - 1 && dst2 + dst[i2 + 1] <= k; i2++)
		{
			dst2 += dst[i2 + 1];
		}
		ans.pub(i1 + 1);
		rs = i2 + 1;
		i1 = rs;
		i2 = rs;
		dst1 = 0;
		dst2 = 0; 
	}

	cout << ans.size() << "\n";
	for (int i = 0; i < ans.size(); i++)
	{
		cout << ans[i];
		if (i < ans.size() - 1) {cout << " ";}
	}
	cout << "\n";
	return 0;
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ans.size() < s && rs < n)
         ~~~~~~~~~~~^~~
Mountains.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++)
                  ~~^~~~~~~~~~~~
Mountains.cpp:90:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i < ans.size() - 1) {cout << " ";}
       ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 36
• Subtask 5: 0 / 28
• Subtask 6: 0 / 9
• Subtask 7: 0 / 12