oj.uz

Submission #686468

# Submission time Handle Problem Language Result Execution time Memory
686468 2023-01-25T10:05:55 Z opPO Bigger segments (IZhO19_segments) C++17
37 / 100
 186 ms 262144 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define f first
#define s second
#define pb push_back
#define ld long double
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
const ld eps = 1e-6;
const int mod = 1e9 + 7;
const int oo = 2e9;
const ll OO = 2e18;
const int N = 2e5 + 10;

void solve()
{
    int n;
    cin >> n;
    vec<ll> a(n + 1);
    vec<ll> p(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i], p[i] = p[i - 1] + a[i];
    vec<vec<int>> dp(n + 1, vec<int>(n + 1, -oo));
    for (int i = 0; i <= n; i++) dp[0][i] = 0;
    auto get = [&](int l, int r) -> ll
    {
        return p[r] - p[l - 1];
    };
    for (int i = 1; i <= n; i++)
    {
        ll sum = 0;
        for (int j = i; j >= 1; j--)
        {
            sum += a[j];
            int l = 1, r = j;
            while (l < r)
            {
                int m = l + r >> 1;
                if (get(m, j - 1) > sum) l = m + 1;
                else r = m;
            }
            dp[i][i - j + 1] = dp[j - 1][j - l] + 1;
        }
        for (int len = 1; len <= n; len++) dp[i][len] = max(dp[i][len], dp[i][len - 1]);
    }
    cout << dp[n][n];
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

Compilation message

segments.cpp: In function 'void solve()':
segments.cpp:52:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |                 int m = l + r >> 1;
      |                         ~~^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 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 212 KB Output is correct
12 Correct 0 ms 320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 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 212 KB Output is correct
12 Correct 0 ms 320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 1236 KB Output is correct
17 Correct 4 ms 1236 KB Output is correct
18 Correct 4 ms 1236 KB Output is correct
19 Correct 4 ms 1236 KB Output is correct
20 Correct 3 ms 1236 KB Output is correct
21 Correct 4 ms 1236 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 2 ms 580 KB Output is correct
24 Correct 4 ms 1236 KB Output is correct
25 Correct 4 ms 1224 KB Output is correct
26 Correct 3 ms 1220 KB Output is correct
27 Correct 4 ms 1236 KB Output is correct
28 Correct 3 ms 1236 KB Output is correct
29 Correct 5 ms 1216 KB Output is correct
30 Correct 4 ms 1236 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 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 212 KB Output is correct
12 Correct 0 ms 320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 1236 KB Output is correct
17 Correct 4 ms 1236 KB Output is correct
18 Correct 4 ms 1236 KB Output is correct
19 Correct 4 ms 1236 KB Output is correct
20 Correct 3 ms 1236 KB Output is correct
21 Correct 4 ms 1236 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 2 ms 580 KB Output is correct
24 Correct 4 ms 1236 KB Output is correct
25 Correct 4 ms 1224 KB Output is correct
26 Correct 3 ms 1220 KB Output is correct
27 Correct 4 ms 1236 KB Output is correct
28 Correct 3 ms 1236 KB Output is correct
29 Correct 5 ms 1216 KB Output is correct
30 Correct 4 ms 1236 KB Output is correct
31 Correct 175 ms 35740 KB Output is correct
32 Correct 155 ms 35736 KB Output is correct
33 Correct 150 ms 35744 KB Output is correct
34 Correct 160 ms 35748 KB Output is correct
35 Correct 155 ms 35748 KB Output is correct
36 Correct 186 ms 35744 KB Output is correct
37 Correct 105 ms 24964 KB Output is correct
38 Correct 71 ms 16100 KB Output is correct
39 Correct 160 ms 35732 KB Output is correct
40 Correct 154 ms 35744 KB Output is correct
41 Correct 152 ms 35728 KB Output is correct
42 Correct 138 ms 35652 KB Output is correct
43 Correct 180 ms 35724 KB Output is correct
44 Correct 138 ms 35732 KB Output is correct
45 Correct 144 ms 35728 KB Output is correct

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 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 212 KB Output is correct
12 Correct 0 ms 320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 1236 KB Output is correct
17 Correct 4 ms 1236 KB Output is correct
18 Correct 4 ms 1236 KB Output is correct
19 Correct 4 ms 1236 KB Output is correct
20 Correct 3 ms 1236 KB Output is correct
21 Correct 4 ms 1236 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 2 ms 580 KB Output is correct
24 Correct 4 ms 1236 KB Output is correct
25 Correct 4 ms 1224 KB Output is correct
26 Correct 3 ms 1220 KB Output is correct
27 Correct 4 ms 1236 KB Output is correct
28 Correct 3 ms 1236 KB Output is correct
29 Correct 5 ms 1216 KB Output is correct
30 Correct 4 ms 1236 KB Output is correct
31 Correct 175 ms 35740 KB Output is correct
32 Correct 155 ms 35736 KB Output is correct
33 Correct 150 ms 35744 KB Output is correct
34 Correct 160 ms 35748 KB Output is correct
35 Correct 155 ms 35748 KB Output is correct
36 Correct 186 ms 35744 KB Output is correct
37 Correct 105 ms 24964 KB Output is correct
38 Correct 71 ms 16100 KB Output is correct
39 Correct 160 ms 35732 KB Output is correct
40 Correct 154 ms 35744 KB Output is correct
41 Correct 152 ms 35728 KB Output is correct
42 Correct 138 ms 35652 KB Output is correct
43 Correct 180 ms 35724 KB Output is correct
44 Correct 138 ms 35732 KB Output is correct
45 Correct 144 ms 35728 KB Output is correct
46 Runtime error 126 ms 262144 KB Execution killed with signal 9
47 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 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 212 KB Output is correct
12 Correct 0 ms 320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3 ms 1236 KB Output is correct
17 Correct 4 ms 1236 KB Output is correct
18 Correct 4 ms 1236 KB Output is correct
19 Correct 4 ms 1236 KB Output is correct
20 Correct 3 ms 1236 KB Output is correct
21 Correct 4 ms 1236 KB Output is correct
22 Correct 3 ms 852 KB Output is correct
23 Correct 2 ms 580 KB Output is correct
24 Correct 4 ms 1236 KB Output is correct
25 Correct 4 ms 1224 KB Output is correct
26 Correct 3 ms 1220 KB Output is correct
27 Correct 4 ms 1236 KB Output is correct
28 Correct 3 ms 1236 KB Output is correct
29 Correct 5 ms 1216 KB Output is correct
30 Correct 4 ms 1236 KB Output is correct
31 Correct 175 ms 35740 KB Output is correct
32 Correct 155 ms 35736 KB Output is correct
33 Correct 150 ms 35744 KB Output is correct
34 Correct 160 ms 35748 KB Output is correct
35 Correct 155 ms 35748 KB Output is correct
36 Correct 186 ms 35744 KB Output is correct
37 Correct 105 ms 24964 KB Output is correct
38 Correct 71 ms 16100 KB Output is correct
39 Correct 160 ms 35732 KB Output is correct
40 Correct 154 ms 35744 KB Output is correct
41 Correct 152 ms 35728 KB Output is correct
42 Correct 138 ms 35652 KB Output is correct
43 Correct 180 ms 35724 KB Output is correct
44 Correct 138 ms 35732 KB Output is correct
45 Correct 144 ms 35728 KB Output is correct
46 Runtime error 126 ms 262144 KB Execution killed with signal 9
47 Halted 0 ms 0 KB -