oj.uz

Submission #81837

# Submission time Handle Problem Language Result Execution time Memory
81837 2018-10-27T06:49:17 Z tmwilliamlin168 Lightning Conductor (POI11_pio) C++14
81 / 100
 1000 ms 36812 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=5e5;
int n, h[mxN], a[mxN], a1[mxN+1], a2[mxN+1];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> h[i];
		a1[i+1]=max(a[i]=h[i], a1[i]);
		for(int j=0; i-j*j-1>=0; ++j)
			a1[i+1]=max(++a[i-j*j-1], a1[i+1]);
	}
	for(int i=n-1; i>=0; --i) {
		a2[i]=max(a[i]=h[i], a2[i+1]);
		for(int j=0; i+j*j+1<=n-1; ++j)
			a2[i]=max(++a[i+j*j+1], a2[i]);
	}
	for(int i=0; i<n; ++i)
		cout << max(a1[i+1], a2[i])-h[i] << "\n";
}

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1536 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2568 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 3300 KB Output is correct
2 Correct 54 ms 3484 KB Output is correct
3 Correct 59 ms 4088 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 5488 KB Output is correct
2 Correct 104 ms 6316 KB Output is correct
3 Correct 129 ms 7536 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 11880 KB Output is correct
2 Correct 399 ms 13860 KB Output is correct
3 Correct 374 ms 15736 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 22928 KB Output is correct
2 Correct 760 ms 24480 KB Output is correct
3 Correct 709 ms 28572 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 31744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 36812 KB Time limit exceeded
2 Halted 0 ms 0 KB -