Submission #158540

#	Time	Username	Problem	Language	Result	Execution time	Memory
158540		luciocf	Lightning Conductor (POI11_pio)	C++14	100 / 100	159 ms	11192 KiB

pio

#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 (stderr)

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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10