답안 #997619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997619	2024-06-12T14:56:48 Z	Luvidi	Bigger segments (IZhO19_segments)	C++17	27 / 100	1500 ms	71008 KB

segments

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

void solve() {
    int n;
    cin>>n;
    ll a[n+1],pre[n+1];
    pre[0]=0;
    for(int i=0;i<n;i++){
        cin>>a[i+1];
        pre[i+1]=pre[i]+a[i+1];
    }
    ll dp[n+1][n+1];
    int idx[n+1];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            dp[i][j]=1e18;
        }
        idx[i]=1e9;
    }
    dp[0][0]=0;
    idx[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(idx[j-1]>=i)continue;
            for(int x=1;x<=i-idx[j-1];x++){
                if(pre[i]-pre[i-x]>=dp[i-x][j-1]){
                    dp[i][j]=min(dp[i][j],pre[i]-pre[i-x]);
                    idx[j]=min(idx[j],i);
                }
            }
        }
    }
    
    ll ans=0;
    for(int i=1;i<=n;i++){
        if(dp[n][i]<1e18)ans=i;
    }
    cout<<ans;
}

int main() {   
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}

Subtask #1

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct

Subtask #2

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	2 ms	2396 KB	Output is correct
17	Correct	2 ms	2396 KB	Output is correct
18	Correct	6 ms	2396 KB	Output is correct
19	Correct	40 ms	2400 KB	Output is correct
20	Correct	33 ms	2428 KB	Output is correct
21	Correct	5 ms	2396 KB	Output is correct
22	Correct	4 ms	1628 KB	Output is correct
23	Correct	2 ms	1116 KB	Output is correct
24	Correct	6 ms	2396 KB	Output is correct
25	Correct	6 ms	2396 KB	Output is correct
26	Correct	32 ms	2424 KB	Output is correct
27	Correct	19 ms	2396 KB	Output is correct
28	Correct	8 ms	2396 KB	Output is correct
29	Correct	32 ms	2396 KB	Output is correct
30	Correct	31 ms	2392 KB	Output is correct

Subtask #3

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	2 ms	2396 KB	Output is correct
17	Correct	2 ms	2396 KB	Output is correct
18	Correct	6 ms	2396 KB	Output is correct
19	Correct	40 ms	2400 KB	Output is correct
20	Correct	33 ms	2428 KB	Output is correct
21	Correct	5 ms	2396 KB	Output is correct
22	Correct	4 ms	1628 KB	Output is correct
23	Correct	2 ms	1116 KB	Output is correct
24	Correct	6 ms	2396 KB	Output is correct
25	Correct	6 ms	2396 KB	Output is correct
26	Correct	32 ms	2424 KB	Output is correct
27	Correct	19 ms	2396 KB	Output is correct
28	Correct	8 ms	2396 KB	Output is correct
29	Correct	32 ms	2396 KB	Output is correct
30	Correct	31 ms	2392 KB	Output is correct
31	Correct	61 ms	70948 KB	Output is correct
32	Correct	88 ms	71008 KB	Output is correct
33	Correct	702 ms	70996 KB	Output is correct
34	Execution timed out	1524 ms	70912 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-

Subtask #4

0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	2 ms	2396 KB	Output is correct
17	Correct	2 ms	2396 KB	Output is correct
18	Correct	6 ms	2396 KB	Output is correct
19	Correct	40 ms	2400 KB	Output is correct
20	Correct	33 ms	2428 KB	Output is correct
21	Correct	5 ms	2396 KB	Output is correct
22	Correct	4 ms	1628 KB	Output is correct
23	Correct	2 ms	1116 KB	Output is correct
24	Correct	6 ms	2396 KB	Output is correct
25	Correct	6 ms	2396 KB	Output is correct
26	Correct	32 ms	2424 KB	Output is correct
27	Correct	19 ms	2396 KB	Output is correct
28	Correct	8 ms	2396 KB	Output is correct
29	Correct	32 ms	2396 KB	Output is correct
30	Correct	31 ms	2392 KB	Output is correct
31	Correct	61 ms	70948 KB	Output is correct
32	Correct	88 ms	71008 KB	Output is correct
33	Correct	702 ms	70996 KB	Output is correct
34	Execution timed out	1524 ms	70912 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-

Subtask #5

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	2 ms	2396 KB	Output is correct
17	Correct	2 ms	2396 KB	Output is correct
18	Correct	6 ms	2396 KB	Output is correct
19	Correct	40 ms	2400 KB	Output is correct
20	Correct	33 ms	2428 KB	Output is correct
21	Correct	5 ms	2396 KB	Output is correct
22	Correct	4 ms	1628 KB	Output is correct
23	Correct	2 ms	1116 KB	Output is correct
24	Correct	6 ms	2396 KB	Output is correct
25	Correct	6 ms	2396 KB	Output is correct
26	Correct	32 ms	2424 KB	Output is correct
27	Correct	19 ms	2396 KB	Output is correct
28	Correct	8 ms	2396 KB	Output is correct
29	Correct	32 ms	2396 KB	Output is correct
30	Correct	31 ms	2392 KB	Output is correct
31	Correct	61 ms	70948 KB	Output is correct
32	Correct	88 ms	71008 KB	Output is correct
33	Correct	702 ms	70996 KB	Output is correct
34	Execution timed out	1524 ms	70912 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-