oj.uz

Submission #341120

# Submission time Handle Problem Language Result Execution time Memory
341120 2020-12-29T03:16:30 Z Dilshod_Imomov Bigger segments (IZhO19_segments) C++17
13 / 100
 1500 ms 15872 KB 
# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
# define int long long
# define fi first
# define se second
 
using namespace std;
 
const int N = 5e3 + 7;
const int mod = 1e9 + 7;
 
int a[N], sum[N], ans, cnt, n;

map < int, int > used[N], dp[N];

int solve( int pos, int sm ) {
    if ( pos == n + 1 ) {
        return 0;
    }
    if ( used[pos][sm] ) {
        return dp[pos][sm];
    }
    used[pos][sm] = 1;
    int s = 0, mx = 0;
    for ( int i = pos; i <= n; i++ ) {
        s += a[i];
        if ( s >= sm ) {
            mx = max( mx, 1 + solve( i + 1, s ) );
        }
    }
    dp[pos][sm] = mx;
    return mx;
}

int32_t main() {
    speed; 
    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    cout << solve( 1, 0 );
}

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 876 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 1 ms 876 KB Output is correct
13 Correct 1 ms 876 KB Output is correct
14 Correct 1 ms 876 KB Output is correct
15 Correct 1 ms 876 KB Output is correct
16 Correct 1 ms 876 KB Output is correct
17 Correct 283 ms 13004 KB Output is correct
18 Correct 426 ms 15872 KB Output is correct
19 Correct 556 ms 13932 KB Output is correct
20 Execution timed out 1558 ms 15084 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 876 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 1 ms 876 KB Output is correct
13 Correct 1 ms 876 KB Output is correct
14 Correct 1 ms 876 KB Output is correct
15 Correct 1 ms 876 KB Output is correct
16 Correct 1 ms 876 KB Output is correct
17 Correct 283 ms 13004 KB Output is correct
18 Correct 426 ms 15872 KB Output is correct
19 Correct 556 ms 13932 KB Output is correct
20 Execution timed out 1558 ms 15084 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 876 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 1 ms 876 KB Output is correct
13 Correct 1 ms 876 KB Output is correct
14 Correct 1 ms 876 KB Output is correct
15 Correct 1 ms 876 KB Output is correct
16 Correct 1 ms 876 KB Output is correct
17 Correct 283 ms 13004 KB Output is correct
18 Correct 426 ms 15872 KB Output is correct
19 Correct 556 ms 13932 KB Output is correct
20 Execution timed out 1558 ms 15084 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 1 ms 876 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 1 ms 876 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Correct 1 ms 876 KB Output is correct
13 Correct 1 ms 876 KB Output is correct
14 Correct 1 ms 876 KB Output is correct
15 Correct 1 ms 876 KB Output is correct
16 Correct 1 ms 876 KB Output is correct
17 Correct 283 ms 13004 KB Output is correct
18 Correct 426 ms 15872 KB Output is correct
19 Correct 556 ms 13932 KB Output is correct
20 Execution timed out 1558 ms 15084 KB Time limit exceeded
21 Halted 0 ms 0 KB -