Submission #1270697

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270697		sarocdnik	Feast (NOI19_feast)	C++20	71 / 100	69 ms	61000 KiB

feast

#include<bits/stdc++.h>
using namespace std ;
long long suml, sumr, n, res, k, fl, num, a[1000009], dp[1000009], f[2005][2005], g[2005][2005];
bool ngcheck;
void sub1()
{
    suml=0;
    sumr=0;
    ngcheck=false;
    for(int i=1; i<=n; i++)
    {
        if(a[i]<0) ngcheck=true, num=a[i];
        else
        {
            if(ngcheck==false) suml+=a[i];
            if(ngcheck==true) sumr+=a[i];
        }
    }
    if(k==1) cout << max(suml+sumr+num,max(suml,sumr));
    else cout << suml+sumr;
}
void sub2()
{
    dp[0]=0;
    res=-1e18;
    for(int i=1; i<=n; i++)
    {
        dp[i]=max(dp[i-1]+a[i],a[i]);
        res=max(res,dp[i]);
    }
    cout << res;
}
void sol()
{
    // for(int i = 0; i <= n; i++) {
    //     for(int j = 0; j <= k; j++) {
    //         f[i][j] = 0;
    //         g[i][j] = 0;
    //     }
    // }
    //memset(f, -0x3f, sizeof f);
    //memset(g, -0x3f, sizeof g);
    g[0][0] = 0;
    for(int i = 0; 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(g[i-1][j], f[i-1][j-1]) + a[i];
            f[i][j] = max(f[i-1][j], g[i][j]);
        }
    }
    cout << f[n][k];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if(fopen("kd.inp","r"))
    {
        freopen("kd.inp","r",stdin);
        freopen("kd.out","w",stdout);
    }
    cin >> n >> k;
    fl=0;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        if(a[i]<0) fl++;
    }
    if(fl<=1) sub1();
    else if(k==1) sub2();
    else sol();
    return 0 ;
}

Compilation message (stderr)

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

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