oj.uz

Submission #1101088

# Submission time Handle Problem Language Result Execution time Memory
1101088 2024-10-15T13:18:48 Z trie Feast (NOI19_feast) C++17
25 / 100
 34 ms 19272 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define ii pair<int, int>
#define iii pair<ii, int>
#define ll long long
#define pb push_back
#define pli pair<ll, int>
#define all(v) (v).begin(), (v).end()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define cntbit(mask) __builtin_popcount(mask)
#define getbit(x, i) ((x >> i) & 1)
#define MASK(i) (1 << i)
#define pli pair<ll, int>
using namespace std;

template<class T1, class T2>
bool maximize(T1 &a, T2 b){if(a < b){a = b; return 1;} return 0;}

template<class T1, class T2>
bool minimize(T1 &a, T2 b){if(a > b){a = b; return 1;} return 0;}

const int N = 505;
const int V = 3e5 + 5;
const int MOD = 1e9 + 7;

int n, k;
ll pr[V], dp[N][N], mx[N][N], a[V];
int negative, idx;

void solve() {
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        pr[i] = pr[i - 1] + a[i];
        if (a[i] < 0) {
            negative++;
            idx = i;
        }
    }

    if (!negative) return cout << pr[n], void();
    /*if (k == 1) { // kadane algorithm.
        ll sum = 0, mxsum = 0;
        for(int i = 1 ; i <= n ; i++) {
            sum += a[i];
            maximize(mxsum, sum);
            if (sum < 0) sum = 0;
        }
        return cout << mxsum, void();
    }
    if (negative == 1) return cout << pr[n] - a[idx], void();*/

    for(int i = 1 ; i <= n ; i++) mx[i][0] = max(mx[i - 1][0], - pr[i]);

    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++) {
            dp[i][j] = dp[i - 1][j];
            maximize(dp[i][j], mx[i][j - 1] + pr[i]);
            mx[i][j] = max(mx[i - 1][j], dp[i][j] - pr[i]);
        }

    cout << dp[n][k];
}

int main(void) {
    //freopen("task.inp", "r", stdin);
    //freopen("task.out", "w", stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    int t = 1; while(t--) solve();
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9652 KB Output is correct
2 Correct 22 ms 9800 KB Output is correct
3 Correct 25 ms 9800 KB Output is correct
4 Correct 23 ms 9752 KB Output is correct
5 Correct 22 ms 9800 KB Output is correct
6 Correct 28 ms 9800 KB Output is correct
7 Correct 22 ms 9824 KB Output is correct
8 Correct 31 ms 9796 KB Output is correct
9 Correct 23 ms 9748 KB Output is correct
10 Correct 31 ms 9772 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 19272 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 18816 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1104 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1016 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 1 ms 848 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 848 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1104 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1016 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 1 ms 848 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 848 KB Output is correct
11 Correct 3 ms 2640 KB Output is correct
12 Correct 2 ms 2384 KB Output is correct
13 Correct 2 ms 2384 KB Output is correct
14 Correct 2 ms 2640 KB Output is correct
15 Correct 2 ms 2384 KB Output is correct
16 Correct 2 ms 2384 KB Output is correct
17 Correct 2 ms 2640 KB Output is correct
18 Correct 2 ms 2640 KB Output is correct
19 Correct 2 ms 2384 KB Output is correct
20 Correct 2 ms 2812 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1104 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 1 ms 1016 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 1 ms 848 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 2 ms 848 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 848 KB Output is correct
11 Correct 3 ms 2640 KB Output is correct
12 Correct 2 ms 2384 KB Output is correct
13 Correct 2 ms 2384 KB Output is correct
14 Correct 2 ms 2640 KB Output is correct
15 Correct 2 ms 2384 KB Output is correct
16 Correct 2 ms 2384 KB Output is correct
17 Correct 2 ms 2640 KB Output is correct
18 Correct 2 ms 2640 KB Output is correct
19 Correct 2 ms 2384 KB Output is correct
20 Correct 2 ms 2812 KB Output is correct
21 Runtime error 15 ms 13392 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 9652 KB Output is correct
2 Correct 22 ms 9800 KB Output is correct
3 Correct 25 ms 9800 KB Output is correct
4 Correct 23 ms 9752 KB Output is correct
5 Correct 22 ms 9800 KB Output is correct
6 Correct 28 ms 9800 KB Output is correct
7 Correct 22 ms 9824 KB Output is correct
8 Correct 31 ms 9796 KB Output is correct
9 Correct 23 ms 9748 KB Output is correct
10 Correct 31 ms 9772 KB Output is correct
11 Runtime error 25 ms 19272 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -