oj.uz

Submission #113998

# Submission time Handle Problem Language Result Execution time Memory
113998 2019-05-29T14:01:27 Z Bruteforceman Sparklers (JOI17_sparklers) C++11
0 / 100
 2 ms 384 KB 
#include "bits/stdc++.h"
using namespace std;
int X[100010];
int N, K, T;

bool good(long long V) {
	int l = K;
	int r = K;
	double extra = 0.0;
	while(1 < l || r < N) {
		bool side;
		if(l == 1) {
			side = false;
		} else if (r == N) {
			side = true;
		} else {
			if(X[l] - X[l - 1] < X[r + 1] - X[r]) {
				side = true;
			} else {
				side = false;
			}
		}
		int diff = side ? (X[l] - X[l - 1]) : (X[r + 1] - X[r]);
		if(2LL * T * V >= diff) {
			extra += T - double(diff) / (2LL * V);
		} else {
			double need = double(diff) / (2LL * V) - T;
			if(extra < need) return false;
			extra -= need;
		}
		if(side) --l;
		else ++r;
	}
	return true;
}

long long search(long long b, long long e) {
	if(b == e) {
		return b;
	}
	long long mid = (b + e) >> 1;
	if(good(mid)) {
		return search(b, mid);
	} else {
		return search(mid + 1, e);
	}
}


int main(int argc, char const *argv[])
{
	scanf("%d %d %d", &N, &K, &T);
	for(int i = 1; i <= N; i++) {
		scanf("%d", &X[i]);
	}
	if(X[N] == 0) {
		printf("0\n");
		exit(0);
	} 
	printf("%lld\n", search(1, 1000000000));
	return 0;
}

Compilation message

sparklers.cpp: In function 'int main(int, const char**)':
sparklers.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &K, &T);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &X[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 50.0

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