Submission #113645

#	Time	Username	Problem	Language	Result	Execution time	Memory
113645		aminra	Sparklers (JOI17_sparklers)	C++14	50 / 100	25 ms	9856 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++)
		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], (a[j] - a[i] + (j - i) * T - 1) / ((j - i) * T));	
			/*if(dp[i][j] != -1)
			{
				cout << "# " << j - i + 1 << " " << k - i + 1 << " " << T / 2 << endl;
				for (int t = i; t <= j; t++)
					cout << a[t] << " ";
				cout << "\n";
				cout << "---> " << dp[i][j] << "\n";
			}*/
		}
	cout << dp[1][n];
}

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