oj.uz

Submission #290763

# Submission time Handle Problem Language Result Execution time Memory
290763 2020-09-04T12:28:43 Z PKhing Bigger segments (IZhO19_segments) C++14
37 / 100
 1500 ms 2688 KB 
#include<bits/stdc++.h>
#define ll long long
#define ii pair<ll,ll>
using namespace std;
ll tab[500005];
ll qs[500005];
ll dp[500005];
ll bf[500005];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&tab[i]);
        qs[i]=tab[i]+qs[i-1];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(qs[i]-qs[j]>=bf[j]){
                if(dp[i]<dp[j]+1){
                    dp[i]=dp[j]+1;
                    bf[i] = qs[i]-qs[j];
                }
                else if(dp[i]==dp[j]+1){
                    bf[i]=min(bf[i],qs[i]-qs[j]);
                }
            }
        }
        //printf("%lld",dp[i]);
    }
    printf("%lld",dp[n]);

}

Compilation message

segments.cpp: In function 'int main()':
segments.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
segments.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |         scanf("%lld",&tab[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 6 ms 384 KB Output is correct
32 Correct 15 ms 384 KB Output is correct
33 Correct 12 ms 384 KB Output is correct
34 Correct 7 ms 384 KB Output is correct
35 Correct 7 ms 384 KB Output is correct
36 Correct 18 ms 384 KB Output is correct
37 Correct 13 ms 384 KB Output is correct
38 Correct 7 ms 384 KB Output is correct
39 Correct 15 ms 384 KB Output is correct
40 Correct 16 ms 384 KB Output is correct
41 Correct 7 ms 384 KB Output is correct
42 Correct 9 ms 384 KB Output is correct
43 Correct 14 ms 384 KB Output is correct
44 Correct 7 ms 384 KB Output is correct
45 Correct 7 ms 384 KB Output is correct

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 6 ms 384 KB Output is correct
32 Correct 15 ms 384 KB Output is correct
33 Correct 12 ms 384 KB Output is correct
34 Correct 7 ms 384 KB Output is correct
35 Correct 7 ms 384 KB Output is correct
36 Correct 18 ms 384 KB Output is correct
37 Correct 13 ms 384 KB Output is correct
38 Correct 7 ms 384 KB Output is correct
39 Correct 15 ms 384 KB Output is correct
40 Correct 16 ms 384 KB Output is correct
41 Correct 7 ms 384 KB Output is correct
42 Correct 9 ms 384 KB Output is correct
43 Correct 14 ms 384 KB Output is correct
44 Correct 7 ms 384 KB Output is correct
45 Correct 7 ms 384 KB Output is correct
46 Execution timed out 1575 ms 2688 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 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 6 ms 384 KB Output is correct
32 Correct 15 ms 384 KB Output is correct
33 Correct 12 ms 384 KB Output is correct
34 Correct 7 ms 384 KB Output is correct
35 Correct 7 ms 384 KB Output is correct
36 Correct 18 ms 384 KB Output is correct
37 Correct 13 ms 384 KB Output is correct
38 Correct 7 ms 384 KB Output is correct
39 Correct 15 ms 384 KB Output is correct
40 Correct 16 ms 384 KB Output is correct
41 Correct 7 ms 384 KB Output is correct
42 Correct 9 ms 384 KB Output is correct
43 Correct 14 ms 384 KB Output is correct
44 Correct 7 ms 384 KB Output is correct
45 Correct 7 ms 384 KB Output is correct
46 Execution timed out 1575 ms 2688 KB Time limit exceeded
47 Halted 0 ms 0 KB -