답안 #977048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977048	2024-05-07T10:47:59 Z	0pt1mus23	Bigger segments (IZhO19_segments)	C++14	13 / 100	1 ms	600 KB

segments

#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(),v.end()
#define ins insert
#define pb push_back
#define int long long
#define endl '\n'
/*
    m : 11059739 -> l ~23
    p : 4567896467
*/
const int mod =  1e9 +7, sze=2*1e5,inf=LLONG_MAX, prime = 2333;


void gkd(){
    int n;
    cin>>n;
    vector<int> ps(n+1);
    vector<int> arr(n+1);
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        ps[i]+=ps[i-1]+arr[i];
    }
    vector<int> dp(n+1),from(n+1);
    for(int i=1;i<=n;i++){
        from[i]=max(from[i],from[i-1]);
        dp[i]=dp[from[i]]+1;
        int t= lower_bound(all(ps),ps[i]*2 - ps[from[i]]) -ps.begin();
        // cout<<t<<" -> "<<i<<" "<<dp[i]<<" ! "<<ps[i]*2 <<" "<< ps[from[i]]<<endl;
        from[t]=i;
    }
    cout<<dp[n]<<endl;

}

signed main(){
    cin.tie(0)->sync_with_stdio(0);  

    int tt=1; 
    // cin>>tt;
    while(tt--) gkd();
    
    return 0;
}

Subtask #1

13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 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	0 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	344 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	500 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct

Subtask #2

0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 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	0 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	344 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	500 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Runtime error	1 ms	600 KB	Execution killed with signal 6
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 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	0 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	344 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	500 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Runtime error	1 ms	600 KB	Execution killed with signal 6
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 36.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 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	0 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	344 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	500 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Runtime error	1 ms	600 KB	Execution killed with signal 6
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 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	0 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	344 KB	Output is correct
12	Correct	1 ms	344 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	0 ms	500 KB	Output is correct
15	Correct	1 ms	348 KB	Output is correct
16	Runtime error	1 ms	600 KB	Execution killed with signal 6
17	Halted	0 ms	0 KB	-