Submission #166829

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
166829	2019-12-04T08:37:32 Z	dandrozavr	Bigger segments (IZhO19_segments)	C++14	27 / 100	6 ms	2808 KB

segments

/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /&#9680;/   /▐/   /▌/ /▀/ /░/ /&#128293;/   choose  own style!

***IT'S OUR LONG WAY TO THE OIILLLL***


░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀🔥░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/



//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

#include <bits/stdc++.h>

using namespace std;
#include <ext/pb_ds/detail/standard_policies.hpp>'
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;

#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
//#define pi 3.14159265358979323846
#define pii pair < ll , int >
#define pipii pair< int, pair < int , int > >
#define siz(n) (int)(n.size())
#define TIME 1.0 * clock() / CLOCKS_PER_SEC

const int inf=1e9 + 7;
const ll inf18=1e18 + 7;
const int N=1e5 + 7;
const int MN = 2097152;
const int M = 1e9 + 7;
int k, n, m, st, en;

vector < pii > g[N];

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #ifdef Estb_probitie
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif

    int n;
    cin >> n;
    int a[n];
    ll pref[n] = {};

    for (int i = 0; i < n; ++i)
        cin >> a[i];
    pref[0] = a[0];
    for (int i = 1; i < n; ++i)
        pref[i] = pref[i - 1] + a[i];

    int dp[n] = {};
    int st[n] = {};
    dp[0] = 1;
    st[0] = 0;
    int ans = 0;

    for (int i = 0; i < n; ++i)
    {
        ans = max(ans, dp[i]);
        if (i)
            if (dp[i] < dp[i - 1])
            {
                dp[i] = dp[i - 1];
                st[i] = st[i - 1];
            }
        ll ousum = pref[i];
        if (st[i])
            ousum -= pref[st[i] - 1];

        int l = i + 1, r = n;
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if (pref[mid] - pref[i] < ousum)
                l = mid + 1; else r = mid;
        }
        if (l == n) continue;
        dp[l] = dp[i] + 1;
        st[l] = i + 1;
    }

    cout << ans;
}

Compilation message

segments.cpp:35:50: warning: missing terminating ' character
 #include <ext/pb_ds/detail/standard_policies.hpp>'
                                                  ^
segments.cpp:35:50: warning: extra tokens at end of #include directive

Subtask #1
13.0 / 13.0

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

Subtask #2
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	4 ms	2680 KB	Output is correct
3	Correct	4 ms	2680 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	4 ms	2680 KB	Output is correct
6	Correct	5 ms	2728 KB	Output is correct
7	Correct	5 ms	2728 KB	Output is correct
8	Correct	4 ms	2680 KB	Output is correct
9	Correct	4 ms	2680 KB	Output is correct
10	Correct	4 ms	2680 KB	Output is correct
11	Correct	4 ms	2680 KB	Output is correct
12	Correct	4 ms	2680 KB	Output is correct
13	Correct	4 ms	2680 KB	Output is correct
14	Correct	4 ms	2680 KB	Output is correct
15	Correct	4 ms	2680 KB	Output is correct
16	Correct	4 ms	2680 KB	Output is correct
17	Correct	4 ms	2684 KB	Output is correct
18	Correct	4 ms	2680 KB	Output is correct
19	Correct	4 ms	2680 KB	Output is correct
20	Correct	4 ms	2680 KB	Output is correct
21	Correct	4 ms	2676 KB	Output is correct
22	Correct	4 ms	2680 KB	Output is correct
23	Correct	4 ms	2680 KB	Output is correct
24	Correct	4 ms	2680 KB	Output is correct
25	Correct	4 ms	2652 KB	Output is correct
26	Correct	4 ms	2680 KB	Output is correct
27	Correct	4 ms	2680 KB	Output is correct
28	Correct	4 ms	2680 KB	Output is correct
29	Correct	4 ms	2680 KB	Output is correct
30	Correct	4 ms	2680 KB	Output is correct

Subtask #3
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	4 ms	2680 KB	Output is correct
3	Correct	4 ms	2680 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	4 ms	2680 KB	Output is correct
6	Correct	5 ms	2728 KB	Output is correct
7	Correct	5 ms	2728 KB	Output is correct
8	Correct	4 ms	2680 KB	Output is correct
9	Correct	4 ms	2680 KB	Output is correct
10	Correct	4 ms	2680 KB	Output is correct
11	Correct	4 ms	2680 KB	Output is correct
12	Correct	4 ms	2680 KB	Output is correct
13	Correct	4 ms	2680 KB	Output is correct
14	Correct	4 ms	2680 KB	Output is correct
15	Correct	4 ms	2680 KB	Output is correct
16	Correct	4 ms	2680 KB	Output is correct
17	Correct	4 ms	2684 KB	Output is correct
18	Correct	4 ms	2680 KB	Output is correct
19	Correct	4 ms	2680 KB	Output is correct
20	Correct	4 ms	2680 KB	Output is correct
21	Correct	4 ms	2676 KB	Output is correct
22	Correct	4 ms	2680 KB	Output is correct
23	Correct	4 ms	2680 KB	Output is correct
24	Correct	4 ms	2680 KB	Output is correct
25	Correct	4 ms	2652 KB	Output is correct
26	Correct	4 ms	2680 KB	Output is correct
27	Correct	4 ms	2680 KB	Output is correct
28	Correct	4 ms	2680 KB	Output is correct
29	Correct	4 ms	2680 KB	Output is correct
30	Correct	4 ms	2680 KB	Output is correct
31	Correct	5 ms	2680 KB	Output is correct
32	Correct	5 ms	2808 KB	Output is correct
33	Correct	5 ms	2808 KB	Output is correct
34	Correct	6 ms	2808 KB	Output is correct
35	Correct	5 ms	2808 KB	Output is correct
36	Correct	5 ms	2808 KB	Output is correct
37	Incorrect	5 ms	2680 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Subtask #4
0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	4 ms	2680 KB	Output is correct
3	Correct	4 ms	2680 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	4 ms	2680 KB	Output is correct
6	Correct	5 ms	2728 KB	Output is correct
7	Correct	5 ms	2728 KB	Output is correct
8	Correct	4 ms	2680 KB	Output is correct
9	Correct	4 ms	2680 KB	Output is correct
10	Correct	4 ms	2680 KB	Output is correct
11	Correct	4 ms	2680 KB	Output is correct
12	Correct	4 ms	2680 KB	Output is correct
13	Correct	4 ms	2680 KB	Output is correct
14	Correct	4 ms	2680 KB	Output is correct
15	Correct	4 ms	2680 KB	Output is correct
16	Correct	4 ms	2680 KB	Output is correct
17	Correct	4 ms	2684 KB	Output is correct
18	Correct	4 ms	2680 KB	Output is correct
19	Correct	4 ms	2680 KB	Output is correct
20	Correct	4 ms	2680 KB	Output is correct
21	Correct	4 ms	2676 KB	Output is correct
22	Correct	4 ms	2680 KB	Output is correct
23	Correct	4 ms	2680 KB	Output is correct
24	Correct	4 ms	2680 KB	Output is correct
25	Correct	4 ms	2652 KB	Output is correct
26	Correct	4 ms	2680 KB	Output is correct
27	Correct	4 ms	2680 KB	Output is correct
28	Correct	4 ms	2680 KB	Output is correct
29	Correct	4 ms	2680 KB	Output is correct
30	Correct	4 ms	2680 KB	Output is correct
31	Correct	5 ms	2680 KB	Output is correct
32	Correct	5 ms	2808 KB	Output is correct
33	Correct	5 ms	2808 KB	Output is correct
34	Correct	6 ms	2808 KB	Output is correct
35	Correct	5 ms	2808 KB	Output is correct
36	Correct	5 ms	2808 KB	Output is correct
37	Incorrect	5 ms	2680 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Subtask #5
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	2680 KB	Output is correct
2	Correct	4 ms	2680 KB	Output is correct
3	Correct	4 ms	2680 KB	Output is correct
4	Correct	4 ms	2680 KB	Output is correct
5	Correct	4 ms	2680 KB	Output is correct
6	Correct	5 ms	2728 KB	Output is correct
7	Correct	5 ms	2728 KB	Output is correct
8	Correct	4 ms	2680 KB	Output is correct
9	Correct	4 ms	2680 KB	Output is correct
10	Correct	4 ms	2680 KB	Output is correct
11	Correct	4 ms	2680 KB	Output is correct
12	Correct	4 ms	2680 KB	Output is correct
13	Correct	4 ms	2680 KB	Output is correct
14	Correct	4 ms	2680 KB	Output is correct
15	Correct	4 ms	2680 KB	Output is correct
16	Correct	4 ms	2680 KB	Output is correct
17	Correct	4 ms	2684 KB	Output is correct
18	Correct	4 ms	2680 KB	Output is correct
19	Correct	4 ms	2680 KB	Output is correct
20	Correct	4 ms	2680 KB	Output is correct
21	Correct	4 ms	2676 KB	Output is correct
22	Correct	4 ms	2680 KB	Output is correct
23	Correct	4 ms	2680 KB	Output is correct
24	Correct	4 ms	2680 KB	Output is correct
25	Correct	4 ms	2652 KB	Output is correct
26	Correct	4 ms	2680 KB	Output is correct
27	Correct	4 ms	2680 KB	Output is correct
28	Correct	4 ms	2680 KB	Output is correct
29	Correct	4 ms	2680 KB	Output is correct
30	Correct	4 ms	2680 KB	Output is correct
31	Correct	5 ms	2680 KB	Output is correct
32	Correct	5 ms	2808 KB	Output is correct
33	Correct	5 ms	2808 KB	Output is correct
34	Correct	6 ms	2808 KB	Output is correct
35	Correct	5 ms	2808 KB	Output is correct
36	Correct	5 ms	2808 KB	Output is correct
37	Incorrect	5 ms	2680 KB	Output isn't correct
38	Halted	0 ms	0 KB	-

Submission #166829

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 14.0 / 14.0

Subtask #3 0 / 10.0

Subtask #4 0 / 36.0

Subtask #5 0 / 27.0

Subtask #1
13.0 / 13.0

Subtask #2
14.0 / 14.0

Subtask #3
0 / 10.0

Subtask #4
0 / 36.0

Subtask #5
0 / 27.0