Submission #62811

#	Time	Username	Problem	Language	Result	Execution time	Memory
62811		gusfring	Sparklers (JOI17_sparklers)	C++14	30 / 100	4 ms	928 KiB

sparklers

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;

const int MAXN = 205;
 
int n, k;
ll t;
ll x[MAXN];
bool dp[MAXN][MAXN];
 
bool check(ll s){
	memset(dp, 0, sizeof dp);
	dp[k][k] = 1;
	for(int len=2; len<=n; ++len){
		for(int l=0; l<n; ++l){
			int r = l + len - 1;
			if (r >= n) break;
			dp[l][r] = ((dp[l + 1][r] || dp[l][r - 1]) && (x[r] - x[l]) <= 2 * s * (r - l) * t);
		}
	}
	return dp[0][n - 1];
}
 
int main(){
	scanf("%d %d %d", &n, &k, &t);
	k--;
	for(int i=0; i<n; ++i) scanf("%d", &x[i]);
	ll lo = -1, hi = (x[n - 1] + t) / t;
	while (hi - lo > 1) {
		ll mid = (lo + hi) / 2;
		if(check(mid)) hi = mid;
		else lo = mid;
	}
	printf("%lld\n", hi);
	return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:28:30: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'll* {aka long long int*}' [-Wformat=]
  scanf("%d %d %d", &n, &k, &t);
                            ~~^
sparklers.cpp:30:42: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
  for(int i=0; i<n; ++i) scanf("%d", &x[i]);
                                     ~~~~~^
sparklers.cpp:28: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:30:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; ++i) scanf("%d", &x[i]);
                         ~~~~~^~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50