oj.uz

Submission #29551

# Submission time Handle Problem Language Result Execution time Memory
29551 2017-07-20T06:02:08 Z gs14004 Lightning Conductor (POI11_pio) C++14
100 / 100
 233 ms 11796 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11796 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11796 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11796 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 11796 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11796 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 11796 KB Output is correct
2 Correct 16 ms 11796 KB Output is correct
3 Correct 29 ms 11796 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11796 KB Output is correct
2 Correct 29 ms 11796 KB Output is correct
3 Correct 36 ms 11796 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11796 KB Output is correct
2 Correct 69 ms 11796 KB Output is correct
3 Correct 83 ms 11796 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 11796 KB Output is correct
2 Correct 133 ms 11796 KB Output is correct
3 Correct 126 ms 11796 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 11796 KB Output is correct
2 Correct 163 ms 11796 KB Output is correct
3 Correct 206 ms 11796 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 11796 KB Output is correct
2 Correct 179 ms 11796 KB Output is correct
3 Correct 199 ms 11796 KB Output is correct