Submission #1270971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270971		sarocdnik	Feast (NOI19_feast)	C++20	30 / 100	28 ms	63300 KiB

feast

#include <bits/stdc++.h>
// #pragma GCC optimize("O3")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
#define el "\n"
#define N 300007
#define nhap "KD"
#define ll long long
#define MS(Arr, val) memset(Arr, val, sizeof(Arr))
#define fi first
#define se second
#define pb push_back
// #define int long long
template <class T> inline bool maximize(T &r, const T &v) { return r < v ? r = v, 1 : 0; }
template <class T> inline bool minimize(T &r, const T &v) { return r > v ? r = v, 1 : 0; }
// const int dx[4] = {-1, 0, 1, 0};
// const int dy[4] = {0, 1, 0, -1};
using namespace std;
int n, k;
ll a[N];
int cnt = 0;
void fre(){
    if (!fopen(nhap ".inp", "r")) return;
    freopen(nhap ".inp", "r", stdin);
    freopen(nhap ".out", "w", stdout);
}
void sub1(){
    ll suml = 0;
    for (int i = 1; i <= n; i++){
        if (a[i] < 0) break;
        suml += a[i];
    }
    ll sumr = 0;
    for (int i = n; i > 0; i--){
        if (a[i] < 0) break;
        sumr += a[i];
    }
    ll suma = 0;
    for (int i = 1; i <= n; i++){
        suma += a[i];
    }
    if (cnt == 0){
        cout << suma;
        return;
    }
    if (k == 1){
        cout << max({suml, sumr, suma});
        return;
    }
    if (k > 1){
        cout << max({suml + sumr, suma});
        return;
    }
}
void sub2(){
    ll sum1 = 0;
    ll sum2 = 0;
    for (int i = 1; i <= n; i++){
        sum1 += a[i];
        sum2 = max(sum2, sum1);
        if (sum1 < 0) sum1 = 0;
    }
    cout << sum2;
}
ll f[2007][2007], g[2007][2007];
void sub3(){
    MS(f, -0x3f);
    MS(g, -0x3f);
    f[0][0] = 0;
    for (int j = 1; j <= k; j++){
        for (int i = 1; i <= n; i++){
            g[i][j] = max(f[i - 1][j - 1], g[i - 1][j]) + a[i];
            f[i][j] = max(f[i - 1][j], g[i][j]);
        }
    }
    cout << f[n][k];
}
signed main(void){
    cin.tie(0)->sync_with_stdio(0);
    fre();
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        if (a[i] < 0) cnt++;
    }
    if (cnt <= 1) sub1();
    else if (k == 1) sub2();
    else sub3();
    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'void fre()':
feast.cpp:24:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     freopen(nhap ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:25:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     freopen(nhap ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29