oj.uz

Submission #285051

# Submission time Handle Problem Language Result Execution time Memory
285051 2020-08-28T09:31:05 Z lukameladze Discharging (NOI20_discharging) C++14
47 / 100
 880 ms 8824 KB 
# include <bits/stdc++.h>
using namespace std;
long long b[1000005], n,a[1000005],mn,mx,raod,x,w,ww;
pair <long long ,long long > dp[1000005];
int main()
{
	cin>>n;
	a[0]=1e9;
	for (int i=1; i<=n; i++)
	{
		cin>>a[i];
		mx=max(mx,a[i]);
		if (a[i]>a[i-1])
		{
		     ww=1;
		}
	}
//	cout<<ww<<endl;
	if (n>1500)
	{
	    cout<<mx*n<<endl;
	    return 0;
	}
	dp[0]={0,0};
	dp[1]={a[1]+(n-1)*a[1],a[1]};
	for (int i=2; i<=n; i++)
	{
		dp[i].first=1e18;
		x=0;
		for (int j=i; j>=1; j--)
		{
			x=max(x,a[j]);
			dp[i].first=min(dp[i].first, dp[j-1].first+(n-j+1)*x);
			
		}
	}
	cout<<dp[n].first;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 416 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 4 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Incorrect 510 ms 8824 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 839 ms 8112 KB Output is correct
2 Correct 880 ms 8184 KB Output is correct
3 Correct 831 ms 8184 KB Output is correct
4 Correct 871 ms 8184 KB Output is correct
5 Correct 864 ms 8284 KB Output is correct
6 Correct 853 ms 8216 KB Output is correct
7 Correct 827 ms 8184 KB Output is correct
8 Correct 840 ms 8244 KB Output is correct
9 Correct 834 ms 8232 KB Output is correct
10 Correct 845 ms 8124 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 416 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 4 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 4 ms 384 KB Output is correct
30 Correct 3 ms 384 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 3 ms 384 KB Output is correct
34 Correct 3 ms 384 KB Output is correct
35 Correct 3 ms 384 KB Output is correct
36 Correct 3 ms 384 KB Output is correct
37 Correct 3 ms 384 KB Output is correct
38 Correct 3 ms 384 KB Output is correct
39 Correct 3 ms 384 KB Output is correct
40 Correct 3 ms 384 KB Output is correct
41 Correct 4 ms 384 KB Output is correct
42 Correct 3 ms 384 KB Output is correct
43 Correct 5 ms 384 KB Output is correct
44 Correct 3 ms 384 KB Output is correct
45 Correct 6 ms 384 KB Output is correct
46 Correct 4 ms 384 KB Output is correct
47 Correct 4 ms 384 KB Output is correct
48 Correct 3 ms 384 KB Output is correct
49 Correct 5 ms 384 KB Output is correct
50 Correct 3 ms 384 KB Output is correct

Subtask #6
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 416 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 4 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 4 ms 384 KB Output is correct
20 Correct 3 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 3 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 3 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 4 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 4 ms 384 KB Output is correct
29 Correct 4 ms 384 KB Output is correct
30 Incorrect 510 ms 8824 KB Output isn't correct
31 Halted 0 ms 0 KB -