Submission #997764

#	Time	Username	Problem	Language	Result	Execution time	Memory
997764		lovrot	Sparklers (JOI17_sparklers)	C++17	0 / 100	4 ms	4188 KiB

sparklers

#include <cstdio> 
#include <algorithm>
#include <cstring>

using namespace std; 

typedef long long ll;

const int N = 1010;
const int OO = 2e9 + 10;

int n, t, k, X[N];

int dp[N][N];

bool solve(int l, int r, int s) {
	if(l < 0 || r >= n || X[r] - X[l] > (ll) (r - l) * t * 2 * s) { return 0; } 
	if(dp[l][r] != -1) { return 1; }

	return dp[l][r] = solve(l - 1, r, s) | solve(l, r + 1, s);
}

int main() { 
	scanf("%d%d%d", &n, &k, &t);
	for(int i = 0; i < n; ++i) { scanf("%d", X + i); }
	
	int lo = -1, hi = OO;
	for(int mi = (lo + hi) / 2; hi - lo > 1; mi = (lo + hi) / 2) {
		memset(dp, -1, sizeof(dp)); dp[0][n - 1] = 1;
		if(solve(k - 1, k - 1, mi)) { hi = mi; }
		else { lo = mi; }
	}

	printf("%d\n", hi);
	return 0;
}

Compilation message (stderr)

sparklers.cpp: In function 'bool solve(int, int, int)':
sparklers.cpp:20:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   20 |  return dp[l][r] = solve(l - 1, r, s) | solve(l, r + 1, s);
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  scanf("%d%d%d", &n, &k, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:25:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  for(int i = 0; i < n; ++i) { scanf("%d", X + i); }
      |                               ~~~~~^~~~~~~~~~~~~

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