oj.uz

답안 #563519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
563519 2022-05-17T11:45:53 Z zxcvbnm Lightning Conductor (POI11_pio) C++14
0 / 100
 1000 ms 9044 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void self_max(int& me, int other) {
	me = max(me, other);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<int> a(n);
	for(int& i : a) {
		cin >> i;
	}
	
	vector<int> ans(n, 0);
	
	for(int sz = 1, p = 1; p*p < n; p++, sz = p*p) {
		multiset<int> s(a.begin(), a.begin()+sz);
		
		auto rem = [&](int x) {
			s.erase(s.find(x));
		};

		//if (sz == 1) cout << p << " " << a[sz] << " " << *s.rend() << ": " << (p - a[sz] + *s.rend()) << "\n";
		self_max(ans[sz], p - a[sz] + *s.rbegin());
		
		for(int r = sz; r < n; r++) {
			rem(a[r-sz]);
			s.insert(a[r]);
			
			//if (r-sz == 1) cout << p << " " << a[r-sz] << " " << *s.rend() << "\n";

			self_max(ans[r-sz], p - a[r-sz] + *s.rbegin());
			if (r != n-1) {
				self_max(ans[r+1], p - a[r+1] + *s.rbegin());
				//if (r+1 == 1) cout << p << " " << a[r+1] << " " << *s.rend() << "\n";
			}
		}
		
		//for(int i : s) {
			//cout << i << " ";
		//}
		//cout << "\n";
	}
	
	multiset<int> s;
	for(int i = 0; i < n-1; i++) {
		s.insert(a[i]);
		//cout << i+1 << ": " << ceil(sqrt(i+1)) << " " << a[i+1] << " " << *s.rbegin() << "\n";
		self_max(ans[i+1], ceil(sqrt(i+1)) - a[i+1] + *s.rbegin());
	}
	
	s.clear();
	for(int i = n-1; i >= 1; i--) {
		s.insert(a[i]);
		self_max(ans[i-1], ceil(sqrt(n-i)) - a[i-1] + *s.rbegin());
	}
	
	for(int i = 0; i < n; i++) {
		cout << ans[i] << "\n";
	}
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1083 ms 2168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1086 ms 1756 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1085 ms 1916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1080 ms 2272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1069 ms 4624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1078 ms 6672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1084 ms 9044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1074 ms 9044 KB Time limit exceeded
2 Halted 0 ms 0 KB -