Submission #683084

#	Time	Username	Problem	Language	Result	Execution time	Memory
683084		rainboy	Sparklers (JOI17_sparklers)	C11	50 / 100	36 ms	3892 KiB

sparklers

#include <stdio.h>

#define N	1000
#define INF	0x3f3f3f3f

long long min(long long a, long long b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int solve(int *xx, int n, int i, int b) {
	static int dp[N][N];
	int l, r;

	for (l = i; l >= 0; l--)
		for (r = i; r < n; r++) {
			dp[l][r] = -1;
			if (l == i && r == i)
				dp[l][r] = b;
			else {
				if (l < i && dp[l + 1][r] >= xx[l + 1] - xx[l])
					dp[l][r] = max(dp[l][r], min(dp[l + 1][r] - (xx[l + 1] - xx[l]) + b, INF));
				if (r > i && dp[l][r - 1] >= xx[r] - xx[r - 1])
					dp[l][r] = max(dp[l][r], min(dp[l][r - 1] - (xx[r] - xx[r - 1]) + b, INF));
			}
		}
	return dp[0][n - 1] >= 0;
}

int main() {
	static int xx[N];
	int n, i_, t, i, lower, upper;

	scanf("%d%d%d", &n, &i_, &t), i_--;
	for (i = 0; i < n; i++)
		scanf("%d", &xx[i]);
	lower = -1, upper = INF;
	while (upper - lower > 1) {
		int s = (lower + upper) / 2;

		if (solve(xx, n, i_, min((long long) t * s * 2, INF)))
			upper = s;
		else
			lower = s;
	}
	printf("%d\n", upper);
	return 0;
}

Compilation message (stderr)

sparklers.c: In function 'main':
sparklers.c:32:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d%d%d", &n, &i_, &t), i_--;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.c:34:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~

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