oj.uz

Submission #1106137

# Submission time Handle Problem Language Result Execution time Memory
1106137 2024-10-29T11:03:10 Z manhlinh1501 Feast (NOI19_feast) C++17
21 / 100
 1000 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

template<class X, class Y>
bool minimize(X &x, const Y &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template<class X, class Y>
bool maximize(X &x, const Y &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

const int MAXN = 3e5 + 5;
const int oo32 = 1e9 + 5;
const i64 oo64 = 1e18 + 5;

int N, K;
i64 a[MAXN];

namespace subtask1 {
    bool is_subtask() {
        for(int i = 1; i <= N; i++) {
            if(a[i] < 0) return false;
        }
        return true;
    }
    void solution() {
        if(is_subtask() == false) return;
        i64 ans = accumulate(a + 1, a + N + 1, 0LL);
        cout << ans;
        exit(0);
    }
}

namespace subtask2 {
    bool is_subtask() {
        int c = 0;
        for(int i = 1; i <= N; i++)
            c += (a[i] < 0);
        return c <= 1;
    }

    void solution() {
        if(is_subtask() == false) return;
        i64 tot = accumulate(a + 1, a + N + 1, 0LL);
        i64 ans = tot;
        for(int i = 1; i <= N; i++) ans = max(ans, tot - a[i]);
        cout << ans;
        exit(0);
    }
}

namespace subtask3 {
    bool is_subtask() {
        return K == 1;
    }
    i64 dp[MAXN];

    void solution() {
        if(is_subtask() == false) return;
        for(int i = 1; i <= N; i++) dp[i] = max(dp[i - 1], 0LL) + a[i];
        cout << *max_element(dp + 1, dp + N + 1);
        exit(0);
    }
}

namespace subtask {
    void solution() {
        for(int i = 1; i <= N; i++) a[i] += a[i - 1];
        vector<vector<i64>> dp(N + 1, vector<i64>(K + 1, -oo64));
        dp[0][0] = 0;
        for(int i = 1; i <= N; i++) {
            for(int x = 1; x <= i; x++) {
                for(int y = x; y <= i; y++) {
                    /// x <= y <= i
                    for(int j = 1; j <= K; j++)
                        maximize(dp[i][j], dp[x - 1][j - 1] + a[i] - a[y - 1]);
                }
            }
        }
        i64 ans = 0;
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= K; j++)
                maximize(ans, dp[i][j]);
        }
        cout << ans;
    }
}

signed main() {
#define task "code"
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> K;
    for(int i = 1; i <= N; i++) cin >> a[i];
//    subtask1::solution();
//    subtask3::solution();
//    subtask2::solution();
    subtask::solution();
    return (0 ^ 0);
}

Compilation message

feast.cpp: In function 'int main()':
feast.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1043 ms 18768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 19016 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 8 ms 2560 KB Output is correct
3 Correct 1 ms 2548 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 3 ms 2384 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 2 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 2 ms 2384 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 8 ms 2560 KB Output is correct
3 Correct 1 ms 2548 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 3 ms 2384 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 2 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 2 ms 2384 KB Output is correct
11 Correct 177 ms 2388 KB Output is correct
12 Correct 202 ms 2640 KB Output is correct
13 Correct 68 ms 2384 KB Output is correct
14 Correct 162 ms 2384 KB Output is correct
15 Correct 117 ms 2384 KB Output is correct
16 Correct 85 ms 2384 KB Output is correct
17 Correct 202 ms 2812 KB Output is correct
18 Correct 16 ms 2384 KB Output is correct
19 Correct 46 ms 2384 KB Output is correct
20 Correct 37 ms 2552 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 8 ms 2560 KB Output is correct
3 Correct 1 ms 2548 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 3 ms 2384 KB Output is correct
6 Correct 2 ms 2516 KB Output is correct
7 Correct 2 ms 2384 KB Output is correct
8 Correct 2 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 2 ms 2384 KB Output is correct
11 Correct 177 ms 2388 KB Output is correct
12 Correct 202 ms 2640 KB Output is correct
13 Correct 68 ms 2384 KB Output is correct
14 Correct 162 ms 2384 KB Output is correct
15 Correct 117 ms 2384 KB Output is correct
16 Correct 85 ms 2384 KB Output is correct
17 Correct 202 ms 2812 KB Output is correct
18 Correct 16 ms 2384 KB Output is correct
19 Correct 46 ms 2384 KB Output is correct
20 Correct 37 ms 2552 KB Output is correct
21 Execution timed out 1049 ms 5456 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 189 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -