oj.uz

Submission #989138

# Submission time Handle Problem Language Result Execution time Memory
989138 2024-05-27T15:19:20 Z Chal1k Bigger segments (IZhO19_segments) C++14
37 / 100
 1500 ms 262144 KB 
#include <bits/stdc++.h>
#include <math.h>
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

#define SPEED ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define str string
#define pb push_back
#define pf push_front
#define nl "\n"
#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
#define len(a) a.size()
#define sz(v) (int)(v.size())
#define pii pair<int,int>
const int N = 5e5 + 1;
const int md = 998244353;
const int mod = 1e9 + 7;
const int mega = 1e6 + 3;
const int inf = 1e9;
int n , a[N + 1] , dp[3005][3005] , pref[N] , suf[3005][3005];
void solve(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> a[i] , pref[i] = pref[i - 1] + a[i];
    for(int i = 0; i <= n; ++i){
        for(int j = 0; j <= n; ++j){
            dp[i][j] = suf[i][j] =  -inf;
        }
    }
    suf[1][1] = 1;
    for(int i = 1; i <= n; ++ i) dp[1][i] = 1;
    for(int i = 2; i <= n; ++i){
        for(int j = i; j >= 1; j--){
            int  l = 1 , r = j - 1 , res = -1;
            while(l <= r){
                int m = (l + r) / 2;
                if(pref[j - 1] - pref[m - 1] <= pref[i] - pref[j - 1]){
                    r = m - 1;
                    res = m;
                }
                else l = m + 1;
            }
            if(res != -1)dp[j][i] = max(dp[j][i] , suf[res][j - 1] + 1);
        }
        suf[i][i] = dp[i][i];
        for(int j = i - 1; j >= 1; --j)suf[j][i] = max(dp[j][i], suf[j + 1][i]);
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i)ans = max(dp[i][n] , ans);
    cout << ans << nl;
}
signed main(){
    SPEED;
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    #ifndef ONLINE_JUDGE
    cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    #endif
}

Subtask #1
13.0 / 13.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 5 ms 26972 KB Output is correct
17 Correct 5 ms 26972 KB Output is correct
18 Correct 5 ms 26972 KB Output is correct
19 Correct 5 ms 27212 KB Output is correct
20 Correct 4 ms 26972 KB Output is correct
21 Correct 5 ms 26972 KB Output is correct
22 Correct 4 ms 22876 KB Output is correct
23 Correct 3 ms 18976 KB Output is correct
24 Correct 6 ms 26972 KB Output is correct
25 Correct 5 ms 27216 KB Output is correct
26 Correct 4 ms 26972 KB Output is correct
27 Correct 5 ms 26972 KB Output is correct
28 Correct 5 ms 26968 KB Output is correct
29 Correct 4 ms 26972 KB Output is correct
30 Correct 5 ms 26972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 5 ms 26972 KB Output is correct
17 Correct 5 ms 26972 KB Output is correct
18 Correct 5 ms 26972 KB Output is correct
19 Correct 5 ms 27212 KB Output is correct
20 Correct 4 ms 26972 KB Output is correct
21 Correct 5 ms 26972 KB Output is correct
22 Correct 4 ms 22876 KB Output is correct
23 Correct 3 ms 18976 KB Output is correct
24 Correct 6 ms 26972 KB Output is correct
25 Correct 5 ms 27216 KB Output is correct
26 Correct 4 ms 26972 KB Output is correct
27 Correct 5 ms 26972 KB Output is correct
28 Correct 5 ms 26968 KB Output is correct
29 Correct 4 ms 26972 KB Output is correct
30 Correct 5 ms 26972 KB Output is correct
31 Correct 144 ms 142676 KB Output is correct
32 Correct 127 ms 142676 KB Output is correct
33 Correct 148 ms 142872 KB Output is correct
34 Correct 153 ms 142676 KB Output is correct
35 Correct 145 ms 142672 KB Output is correct
36 Correct 175 ms 142928 KB Output is correct
37 Correct 120 ms 120668 KB Output is correct
38 Correct 70 ms 88996 KB Output is correct
39 Correct 163 ms 142672 KB Output is correct
40 Correct 144 ms 142672 KB Output is correct
41 Correct 124 ms 142684 KB Output is correct
42 Correct 132 ms 142676 KB Output is correct
43 Correct 138 ms 142672 KB Output is correct
44 Correct 143 ms 142680 KB Output is correct
45 Correct 140 ms 142888 KB Output is correct

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 5 ms 26972 KB Output is correct
17 Correct 5 ms 26972 KB Output is correct
18 Correct 5 ms 26972 KB Output is correct
19 Correct 5 ms 27212 KB Output is correct
20 Correct 4 ms 26972 KB Output is correct
21 Correct 5 ms 26972 KB Output is correct
22 Correct 4 ms 22876 KB Output is correct
23 Correct 3 ms 18976 KB Output is correct
24 Correct 6 ms 26972 KB Output is correct
25 Correct 5 ms 27216 KB Output is correct
26 Correct 4 ms 26972 KB Output is correct
27 Correct 5 ms 26972 KB Output is correct
28 Correct 5 ms 26968 KB Output is correct
29 Correct 4 ms 26972 KB Output is correct
30 Correct 5 ms 26972 KB Output is correct
31 Correct 144 ms 142676 KB Output is correct
32 Correct 127 ms 142676 KB Output is correct
33 Correct 148 ms 142872 KB Output is correct
34 Correct 153 ms 142676 KB Output is correct
35 Correct 145 ms 142672 KB Output is correct
36 Correct 175 ms 142928 KB Output is correct
37 Correct 120 ms 120668 KB Output is correct
38 Correct 70 ms 88996 KB Output is correct
39 Correct 163 ms 142672 KB Output is correct
40 Correct 144 ms 142672 KB Output is correct
41 Correct 124 ms 142684 KB Output is correct
42 Correct 132 ms 142676 KB Output is correct
43 Correct 138 ms 142672 KB Output is correct
44 Correct 143 ms 142680 KB Output is correct
45 Correct 140 ms 142888 KB Output is correct
46 Execution timed out 2466 ms 262144 KB Time limit exceeded
47 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 5 ms 26972 KB Output is correct
17 Correct 5 ms 26972 KB Output is correct
18 Correct 5 ms 26972 KB Output is correct
19 Correct 5 ms 27212 KB Output is correct
20 Correct 4 ms 26972 KB Output is correct
21 Correct 5 ms 26972 KB Output is correct
22 Correct 4 ms 22876 KB Output is correct
23 Correct 3 ms 18976 KB Output is correct
24 Correct 6 ms 26972 KB Output is correct
25 Correct 5 ms 27216 KB Output is correct
26 Correct 4 ms 26972 KB Output is correct
27 Correct 5 ms 26972 KB Output is correct
28 Correct 5 ms 26968 KB Output is correct
29 Correct 4 ms 26972 KB Output is correct
30 Correct 5 ms 26972 KB Output is correct
31 Correct 144 ms 142676 KB Output is correct
32 Correct 127 ms 142676 KB Output is correct
33 Correct 148 ms 142872 KB Output is correct
34 Correct 153 ms 142676 KB Output is correct
35 Correct 145 ms 142672 KB Output is correct
36 Correct 175 ms 142928 KB Output is correct
37 Correct 120 ms 120668 KB Output is correct
38 Correct 70 ms 88996 KB Output is correct
39 Correct 163 ms 142672 KB Output is correct
40 Correct 144 ms 142672 KB Output is correct
41 Correct 124 ms 142684 KB Output is correct
42 Correct 132 ms 142676 KB Output is correct
43 Correct 138 ms 142672 KB Output is correct
44 Correct 143 ms 142680 KB Output is correct
45 Correct 140 ms 142888 KB Output is correct
46 Execution timed out 2466 ms 262144 KB Time limit exceeded
47 Halted 0 ms 0 KB -