oj.uz

Submission #224550

# Submission time Handle Problem Language Result Execution time Memory
224550 2020-04-18T11:47:13 Z Berted Mountains (NOI20_mountains) C++14
0 / 100
 2000 ms 52600 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 52600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 52600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 39056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2083 ms 39056 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 52600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -