oj.uz

Submission #1103120

# Submission time Handle Problem Language Result Execution time Memory
1103120 2024-10-20T07:18:49 Z khoaha123 Feast (NOI19_feast) C++17
32 / 100
 510 ms 7896 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7760 KB Output is correct
2 Correct 29 ms 7760 KB Output is correct
3 Correct 26 ms 7760 KB Output is correct
4 Correct 22 ms 7828 KB Output is correct
5 Correct 20 ms 7760 KB Output is correct
6 Correct 28 ms 7748 KB Output is correct
7 Correct 20 ms 7780 KB Output is correct
8 Correct 22 ms 7676 KB Output is correct
9 Correct 22 ms 7760 KB Output is correct
10 Correct 22 ms 7760 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 7760 KB Output is correct
2 Incorrect 14 ms 7820 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7756 KB Output is correct
2 Correct 25 ms 7760 KB Output is correct
3 Correct 23 ms 7760 KB Output is correct
4 Correct 32 ms 7812 KB Output is correct
5 Correct 24 ms 7760 KB Output is correct
6 Correct 23 ms 7896 KB Output is correct
7 Correct 25 ms 7760 KB Output is correct
8 Correct 23 ms 7760 KB Output is correct
9 Correct 25 ms 7792 KB Output is correct
10 Correct 25 ms 7760 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 510 ms 6648 KB Output is correct
3 Correct 8 ms 6480 KB Output is correct
4 Correct 12 ms 6480 KB Output is correct
5 Correct 56 ms 6660 KB Output is correct
6 Correct 48 ms 6480 KB Output is correct
7 Correct 32 ms 6480 KB Output is correct
8 Correct 9 ms 6648 KB Output is correct
9 Correct 2 ms 2384 KB Output is correct
10 Correct 14 ms 6480 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 510 ms 6648 KB Output is correct
3 Correct 8 ms 6480 KB Output is correct
4 Correct 12 ms 6480 KB Output is correct
5 Correct 56 ms 6660 KB Output is correct
6 Correct 48 ms 6480 KB Output is correct
7 Correct 32 ms 6480 KB Output is correct
8 Correct 9 ms 6648 KB Output is correct
9 Correct 2 ms 2384 KB Output is correct
10 Correct 14 ms 6480 KB Output is correct
11 Incorrect 1 ms 2384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 510 ms 6648 KB Output is correct
3 Correct 8 ms 6480 KB Output is correct
4 Correct 12 ms 6480 KB Output is correct
5 Correct 56 ms 6660 KB Output is correct
6 Correct 48 ms 6480 KB Output is correct
7 Correct 32 ms 6480 KB Output is correct
8 Correct 9 ms 6648 KB Output is correct
9 Correct 2 ms 2384 KB Output is correct
10 Correct 14 ms 6480 KB Output is correct
11 Incorrect 1 ms 2384 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7760 KB Output is correct
2 Correct 29 ms 7760 KB Output is correct
3 Correct 26 ms 7760 KB Output is correct
4 Correct 22 ms 7828 KB Output is correct
5 Correct 20 ms 7760 KB Output is correct
6 Correct 28 ms 7748 KB Output is correct
7 Correct 20 ms 7780 KB Output is correct
8 Correct 22 ms 7676 KB Output is correct
9 Correct 22 ms 7760 KB Output is correct
10 Correct 22 ms 7760 KB Output is correct
11 Correct 14 ms 7760 KB Output is correct
12 Incorrect 14 ms 7820 KB Output isn't correct
13 Halted 0 ms 0 KB -