oj.uz

Submission #113643

# Submission time Handle Problem Language Result Execution time Memory
113643 2019-05-27T10:32:38 Z aminra Sparklers (JOI17_sparklers) C++14
0 / 100
 2 ms 384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -