oj.uz

Submission #158539

# Submission time Handle Problem Language Result Execution time Memory
158539 2019-10-17T16:37:20 Z luciocf Lightning Conductor (POI11_pio) C++14
91 / 100
 162 ms 15348 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5+10;

int n;
int h[maxn];

int L[maxn], R[maxn];

void get_candidates(void)
{
	int last = 0;

	for (int i = 1; i <= n; i++)
	{
		if (h[i] <= last) continue;
		last = h[i];

		for (int d = 1; i + (d-1)*(d-1) + 1 <= n; d++)
		{
			int p = i + (d-1)*(d-1) + 1;
			L[p] = max(L[p], h[i]+d);
		}
	}

	last = 0;

	for (int i = n; i >= 1; i--)
	{
		if (h[i] <= last) continue;
		last = h[i];

		for (int d = 1; i - (d-1)*(d-1) - 1 > 0; d++)
		{
			int p = i - (d-1)*(d-1) - 1;
			R[p] = max(R[p], h[i]+d);
		}
	}
}

int main(void)
{
	scanf("%d", &n);

	for (int i = 1; i <= n; i++)
		scanf("%d", &h[i]);

	get_candidates();

	for (int i = 1; i <= n; i++) L[i] = max(L[i-1], L[i]);
	for (int i = n; i >= 1; i--) R[i] = max(R[i+1], R[i]);

	for (int i = 1; i <= n; i++)
		printf("%d\n", max(0, max(R[i], L[i])-h[i]));
}

Compilation message

pio.cpp: In function 'int main()':
pio.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
pio.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &h[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1272 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1916 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2040 KB Output is correct
2 Incorrect 14 ms 1428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2844 KB Output is correct
2 Correct 27 ms 2840 KB Output is correct
3 Correct 31 ms 3064 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6364 KB Output is correct
2 Correct 58 ms 6008 KB Output is correct
3 Correct 62 ms 6008 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 11256 KB Output is correct
2 Correct 92 ms 9336 KB Output is correct
3 Correct 100 ms 10020 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 15348 KB Output is correct
2 Correct 133 ms 13176 KB Output is correct
3 Correct 151 ms 14072 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 13008 KB Output is correct
2 Correct 129 ms 13108 KB Output is correct
3 Correct 146 ms 14072 KB Output is correct