Submission #113643

#	Time	Username	Problem	Language	Result	Execution time	Memory
113643		aminra	Sparklers (JOI17_sparklers)	C++14	0 / 100	2 ms	384 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1003;
const int infint = (int)2e9;
const ll inf = (ll)2e18;
ll dp[MAXN][MAXN], part[MAXN], a[MAXN], dist[MAXN], n, k, T;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> k >> T;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	T *= 2;
	for (int i = 1; i <= n; i++)
		dist[i] = abs(a[i] - a[k]);
	
	part[1] = dist[1];
	for (int i = 2; i <= n; i++)
		part[i] = part[i - 1] + dist[i];
	
	for (int i = 1; i <= n; i++)
		dp[i][i] = -1;
	
	dp[k][k] = 0;
	for (int len = 1; len < n; len++)
		for (int i = 1; i <= n - len; i++)
		{
			int j = i + len;
			if(dp[i + 1][j] == -1 && dp[i][j - 1] == -1)
				dp[i][j] = -1;
			else
			if(dp[i + 1][j] == -1)
				dp[i][j] = dp[i][j - 1];
			else
			if(dp[i][j - 1] == -1)
				dp[i][j] = dp[i + 1][j];
			else
				dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]);
			if(dp[i][j] != -1)
				dp[i][j] = max(dp[i][j], (part[j] - part[i - 1] + (j - i) * T - 1) / ((j - i) * T));		
		}
	cout << dp[1][n];
}

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