Submission #206144

#	Time	Username	Problem	Language	Result	Execution time	Memory
206144		arnold518	Sparklers (JOI17_sparklers)	C++14	30 / 100	2068 ms	4348 KiB

sparklers

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1000;

int N, K;
ll T, A[MAXN+10], B[MAXN+10];

int dp[MAXN+10][MAXN+10];

int f(int l, int r)
{
	if(l==1 && r==N-1) return 1;
	int ret=dp[l][r];
	if(ret!=-1) return ret;

	ret=0;
	if(l!=1 && B[r]-B[l-2]>=0 && f(l-1, r)==1) ret=1;
	if(r!=N-1 && B[r+1]-B[l-1]>=0 && f(l, r+1)==1) ret=1;
	return ret;
}

bool solve(ll v)
{
	int i, j;

	for(i=1; i<N; i++) B[i]=v*T-(A[i+1]-A[i])/2;
	memset(dp, -1, sizeof(dp));

	for(i=1; i<N; i++) B[i]+=B[i-1];
	return f(K, K-1);
}

int main()
{
	int i, j;

	scanf("%d%d%lld", &N, &K, &T), T*=2;
	for(i=1; i<=N; i++) scanf("%lld", &A[i]), A[i]*=2;

	ll lo=-1, hi=1e10;
	while(lo+1<hi)
	{
		ll mid=lo+hi>>1;
		if(solve(mid)) hi=mid;
		else lo=mid;
	}
	printf("%lld\n", hi);
}

Compilation message (stderr)

sparklers.cpp: In function 'bool solve(ll)':
sparklers.cpp:29:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sparklers.cpp: In function 'int main()':
sparklers.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   ll mid=lo+hi>>1;
          ~~^~~
sparklers.cpp:40:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
sparklers.cpp:42:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &N, &K, &T), T*=2;
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
sparklers.cpp:43:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld", &A[i]), A[i]*=2;
                      ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

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