Submission #1244812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244812		CrabCNH	Kas (COCI17_kas)	C++20	100 / 100	260 ms	198136 KiB

kas

#include <bits/stdc++.h>

#define int long long
#define pii pair <int, int>
#define fi first
#define se second

using namespace std;

const int N = 5e2 + 5;
const int maxval = 1e5 + 5;
const int inf = 1e18 + 7;

int n, sum = 0;
int c[N];
int f[N][maxval / 2];

int dp (int i, int val) {
    if (val > sum / 2) {
        return -inf;
    }
    if (f[i][val] != -1) {
        return f[i][val];
    }
    if (i > n) {
        return f[i][val] = (val != 0) * (-inf);
    }
    int t1 = max ({dp(i + 1, val), dp (i + 1, val + c[i]) + c[i]});
    int t2 = dp (i + 1, abs (val - c[i])) + max (0LL, c[i] - val);
    return (f[i][val] = max (t1, t2));
}

signed main () {
    ios_base :: sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    #define task "crab"
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> c[i]; 
        sum += c[i];
    }
    memset (f, -1, sizeof (f));
    int r = dp (1, 0);
    cout << r + (sum - r * 2);
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10