oj.uz

Submission #749826

# Submission time Handle Problem Language Result Execution time Memory
749826 2023-05-28T15:26:03 Z TheOpChicken Sparklers (JOI17_sparklers) C++17
0 / 100
 1 ms 312 KB 
#include <iostream>
using namespace std;

const long long maxN = 1e5 + 5, inf = 1e9;
long long arr[maxN];

int main(){
	long long n, k, t;
	cin >> n >> k >> t;

	for (int i = 0; i < n; i++) cin >> arr[i];
	k--;

	long long l = 1, r = inf, ans = inf;
	while(l <= r){
		long long mid = (l+r)/2, left_margin = 0, right_margin = 0, went_left = 0, went_right = 0;
		if(mid*t > inf){
			ans = mid;
			r = mid-1;
			continue;
		}

		int left = k, right = k, pos = 1;
		while(pos){
			pos = 0;
			if (left >= 1){
				long long last = arr[k] - 2*(k-(left-1))*mid*t + went_right - went_left;
				long long diff = arr[left-1] - last;
				
				if (last - left_margin <= arr[left-1]){
					pos = 1;
					left--;

					went_left += max(0ll, -diff);
					right_margin = max(0ll, diff);
					
					left_margin += min(0ll, diff);
				}
			}

			if (right < n-1){
				long long last = arr[k] + 2*(right+1-k)*mid*t + went_right - went_left;
				long long diff = last - arr[right+1];
				if (last + right_margin >= arr[right+1]){
					pos = 1;
					right++;

					went_right += max(0ll, -diff);
					left_margin = max(0ll, diff);

					right_margin += min(0ll, diff);
				}
			}
		}

		if (left == 0 && right == n-1){
			ans = mid;
			r = mid-1;
		}

		else l = mid+1;
	}

	cout << ans << endl;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 312 KB Output is correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Halted 0 ms 0 KB -