oj.uz

Submission #158540

# Submission time Handle Problem Language Result Execution time Memory
158540 2019-10-17T16:38:38 Z luciocf Lightning Conductor (POI11_pio) C++14
100 / 100
 159 ms 11192 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 = -1;

	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 = -1;

	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 372 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1016 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1372 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1400 KB Output is correct
2 Correct 14 ms 1400 KB Output is correct
3 Correct 19 ms 2040 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1912 KB Output is correct
2 Correct 26 ms 1912 KB Output is correct
3 Correct 28 ms 2424 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 4088 KB Output is correct
2 Correct 56 ms 3964 KB Output is correct
3 Correct 61 ms 4728 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 7876 KB Output is correct
2 Correct 89 ms 5880 KB Output is correct
3 Correct 97 ms 8008 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 11188 KB Output is correct
2 Correct 125 ms 8184 KB Output is correct
3 Correct 139 ms 11192 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 8684 KB Output is correct
2 Correct 125 ms 8184 KB Output is correct
3 Correct 137 ms 11152 KB Output is correct