Submission #1103120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103120		khoaha123	Feast (NOI19_feast)	C++17	32 / 100	510 ms	7896 KiB

feast

#include <bits/stdc++.h>
#define endl '\n'
#define ii pair<int,int>
#define task ""
#define all(x) x.begin(),x.end()
#define MASK(x) (1 << (x))
#define int long long
using namespace std;
const int N = 3e5 + 5;
const int LOG = 20;
const int mod = 998244353;
const long long INF = 1e18;

int n,a[N],dp[85][85][85],s[N];

int calc(int l,int r,int k){
    if (k == 0) return 0;
    if (l == r) return max(a[l],0LL);
    int &res = dp[l][r][k];
    if (res != -1) return res;
    res = 0;

    for (int i = l; i < r; ++i){
        for (int j = 0; j <= min(k,(i-l+1)); ++j){
            res = max(res,calc(l,i,j) + calc(i+1,r,k-j));
        }
    }
    res = max(res,s[r] - s[l-1]);
    return res;
}
int k;
void subtask1(void){
    int sum = 0;
    for (int i = 1; i <= n; ++i) sum += a[i];
    cout << sum;
}

void subtask2(void){
    int pos = -1;
    for (int i = 1; i <= n; ++i){
        if (a[i] < 0){
            pos = i;break;
        }
    }
    if (k == 1){
        int sum1 = 0,sum2 = 0;
        for (int i = 1; i < pos; ++i) sum1 += a[i];
        for (int i = pos+1; i <= n; ++i) sum2 += a[i];
        cout << max(sum1,sum2);
    }
    else {
        int sum1 = 0,sum2 = 0;
        for (int i = 1; i < pos; ++i) sum1 += a[i];
        for (int i = pos+1; i <= n; ++i) sum2 += a[i];
        cout << sum1 + sum2;
    }
}

void subtask3(void){
    int best = 0;
    int sum = 0;
    for (int i = 1; i <= n; ++i){
        sum = max(a[i],sum + a[i]);
        best = max(best,sum);
    }
    cout << best;
}

void subtask4(void){
    memset(dp,-1,sizeof(dp));

    cout << calc(1,n,k) << endl;

}

long long Rand(long long l, long long r) {
    long long res = 0;
    for (int i= 1; i <= 4; ++i) res = (res << 15) ^ (rand() & ((1 << 15) - 1));
    return l + res % (r-l+1);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        freopen(task".OUT","w",stdout);
    }
    srand(time(NULL));
    cin >> n >> k;


    int sub1 = 0,am = 0;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        //a[i] = Rand(-1000000000,1000000000);
        if (a[i] >= 0) sub1++;
        else am++;
        s[i] = s[i-1] + a[i];
    }

    if (sub1 == n){
        subtask1();
        return 0;
    }
    if (am == 1){
        subtask2();
        return 0;
    }
    if (k == 1){
        subtask3();
        return 0;
    }
    if (n <= 80){
        subtask4();return 0;
    }
    return 0;
}

Compilation message (stderr)

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

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