Submission #1270699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270699		sarocdnik	Feast (NOI19_feast)	C++20	43 / 100	1096 ms	15660 KiB

feast

#include <bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
using namespace std;
#define ll long long
#define vtn 3004
#define fmax 1000007
#define fi first
#define se second
#define sp << " "
#define el << "\n"
#define oo 1e9
// #define int ll
#define pii pair<int,int>
#define pb push_back
#define FOD(i,b,a) for(int i = (int)b; i >= (int)a; i--)
#define FOR(i,a,b) for(int i = (int)a; i <= (int)b; i++)
#define NAME "KD"
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
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;}
//0x3f = oo

int n, k;
ll a[fmax];
ll dp[5007][5007], tl[fmax];
bool ok = 1;
int cnt = 0;
void solve(){

    cin >> n >> k;
    FOR(i,1,n){
        cin >> a[i];
        a[i] < 0 ? cnt++ : 0 ;
    } 
    if(cnt > 1) ok = 0;
    FOR(i,1,n){
        tl[i] = tl[i - 1] + a[i];
    }
    if(ok){
        ll sum1 = 0, sum2 = 0;
        FOR(i,1,n){
            if(a[i] <= 0){
                sum2 = sum1;
                sum1 = 0;
            }else{
                sum1+= a[i];
            }
        }
        if(k == 1) cout << max(sum1, sum2);
        else cout << sum1 + sum2;
    }
    else if(k == 1){
        ll res = 0, mx = 0;
        FOR(i,1,n){
            // cerr << i sp << mx el;
            mx = max(a[i], mx + a[i]);
            res = max(res, mx);
        }
        cout << res;
    }
    else if(n <= 5000 && k <= 5000){
        FOR(i,1,n){
            FOR(j,1,k){
                dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                FOD(f,i,1){
                    dp[i][j] = max(dp[i][j], dp[f - 1][j - 1] + tl[i] - tl[f - 1]);
                }
            }
        }
        cout << dp[n][k];
    }
    // FOR(j,0,k){
    // FOR(i,1,n){
    //         cerr << dp[i][j] sp;
    //     }
    //     cerr el;
    // }
}
signed main(){
    faster
    if(fopen(NAME".inp", "r")){
        freopen(NAME ".inp", "r", stdin);
        freopen(NAME ".out", "w", stdout);
    }
    int test = 1;
    // cin >> test;
    while(test--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

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

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