Submission #1270975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270975		sarocdnik	Feast (NOI19_feast)	C++20	0 / 100	1 ms	328 KiB

feast

#include <bits/stdc++.h>
#define ll long long
#define N
#define fi first
#define se second
#define pb push_back
#define MS(arr, val) memset(arr, val, sizeof(val))
using namespace std;
int n, k;
ll a[300007];
int cnt = 0;
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];
ll g[2007][2007];
void sub3(){
    MS(f, -0x3f);
    MS(g, -0x3f);
    f[0][0] = g[0][0] = 0;
    for(int i = 1; i <= n; i++) f[i][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(){
    cin.tie(0)->sync_with_stdio(0);
    #define nhap "SCHESMAR"
    freopen(nhap".inp", "r", stdin);
    freopen(nhap".out", "w", stdout);
    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();
//    sub2();
//    sub3();
    return 0;
}

Compilation message (stderr)

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

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