Submission #113998

#	Time	Username	Problem	Language	Result	Execution time	Memory
113998		Bruteforceman	Sparklers (JOI17_sparklers)	C++11	0 / 100	2 ms	384 KiB

sparklers

#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 (stderr)

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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50