Submission #837160

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
837160	2023-08-25T05:32:02 Z	12345678	Discharging (NOI20_discharging)	C++17	9 / 100	1000 ms	18424 KB

Discharging

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e6+5;
ll n, t[nx], dp[nx][2];

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>t[i];
    for (int i=1; i<=n; i++)
    {
        ll mx=t[i]; dp[i][0]=dp[i][1]=1e18;
        for (int j=i-1; j>=0; j--)
        {
            if (dp[j][0]+(dp[j][1]+mx)*(i-j)<dp[i][0])
            {
                dp[i][0]=dp[j][0]+(dp[j][1]+mx)*(i-j);
                dp[i][1]=dp[j][1]+mx;
            }
            mx=max(mx, t[j]);
        }
        //cout<<i<<' '<<dp[i][0]<<' '<<dp[i][1]<<'\n';
    }
    cout<<dp[n][0];
}

Subtask #1

9.0 / 9.0

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

Subtask #2

0 / 13.0

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

Subtask #3

0 / 25.0

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

Subtask #4

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1055 ms	18424 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 14.0

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

Subtask #6

0 / 28.0

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