Submission #29551

#	Time	Username	Problem	Language	Result	Execution time	Memory
29551		gs14004	Lightning Conductor (POI11_pio)	C++14	100 / 100	233 ms	11796 KiB

pio

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
const int MAXN = 500005;

double sqr[MAXN], ans[MAXN];
int n, a[MAXN];

void solve(int s, int e, int ps, int pe, int rev){
	if(s > e) return;
	int m = (s+e)/2;
	int opt = -1;
	double mx = -1e9;
	for(int i=ps; i<=pe && i<m; i++){
		double cur = a[i] + sqr[m - i];
		if(cur > mx){
			mx = cur;
			opt = i;
		}
	}
	if(rev) ans[n+1-m] = max(ans[n+1-m], mx);
	else ans[m] = max(ans[m], mx);
	solve(s, m-1, ps, opt, rev);
	solve(m+1, e, opt, pe, rev);
}

int main(){
	scanf("%d",&n);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		sqr[i] = sqrt(i);
	}
	solve(1, n, 1, n, 0);
	reverse(a+1, a+n+1);
	solve(1, n, 1, n, 1);
	reverse(a+1, a+n+1);
	for(int i=1; i<=n; i++){
		int cu = (int)ceil(ans[i]);
		printf("%d\n", max(cu - a[i], 0));
	}
}

Compilation message (stderr)

pio.cpp: In function 'int main()':
pio.cpp:30:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
pio.cpp:32:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[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