oj.uz

Submission #213294

# Submission time Handle Problem Language Result Execution time Memory
213294 2020-03-25T12:22:40 Z patrikpavic2 Sparklers (JOI17_sparklers) C++17
0 / 100
 5 ms 384 KB 
#include <cstdio>
#include <cstring>
#include <vector>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 1e5 + 500;
const ll mil = 1e9;

ll dp_L[N], dp_R[N], k, n;
ll X[N], T, tX[N];

void obrni(){
	for(int i = 0;i < n;i++)
		tX[i] = mil - X[i];
	for(int i = 0;i < n;i++)
		X[i] = tX[n - i - 1];
	k = n - k - 1;
}

bool check(ll s){
	ll i = 0, j = n - 1;
	for(;i < k;i++){
		if(i)
			dp_L[i] = max(dp_L[i - 1] + (X[i] - X[i - 1]) - 2LL * s * T, 0LL);
		else
			dp_L[i] = 0;
	}
	for(;j > k;j--){
		if(j == n - 1)
			dp_R[j] = 0;
		else
			dp_R[j] = max(dp_R[j + 1] + (X[j + 1] - X[j]) - 2LL * s * T, 0LL);
	}
	ll ost_R = 0;
	if(k + 1 < n)
		ost_R = max(dp_R[k + 1] + X[k + 1] - X[k], 0LL);
	//printf("ost_R = %lld\n", ost_R);
	ll sum_ostalo = 0;
	for(ll ii = k;ii >= 0;ii--){
		//printf("dp_L[%lld] = %lld X[%lld] = %lld\n", ii, dp_L[ii], ii, X[ii]);
		ll ostalo = 2LL * s * T;
		if(ii)
			ostalo = 2LL * s * T - (dp_L[ii - 1] + X[ii] - X[ii - 1]);
		//printf("ostalo = %lld\n", ostalo);
		if(sum_ostalo >= dp_L[ii - 1] + X[ii] - X[ii - 1] && sum_ostalo + 2LL * s * T >= ost_R)
			return 1;
		sum_ostalo += ostalo;
		if(sum_ostalo < 0) break;
		if(sum_ostalo >= ost_R)
			return 1;
	}
	//printf("vracam 0\n");
	return 0;
}

bool pravi(int s){
	//printf("prva provjera %d\n", check(s));
	bool ret = check(s);
	obrni(); 
	ret |= check(s);
	//printf("druga provjera %d\n", check(s));
	obrni();
	return ret;
}

int main(){
	scanf("%lld%lld%lld", &n, &k, &T); k--;
	for(int i = 0;i < n;i++)
		scanf("%lld", X + i);
	ll x = 0;
	for(ll i = 30;i >= 0;i--){
		if(!pravi(x + (1LL << i)))
			x += 1LL << i;
	}
	printf("%lld\n", x + 1);
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld", &n, &k, &T); k--;
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", X + i);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 50.0

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