Submission #1300339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1300339		tab	Kas (COCI17_kas)	C++20	0 / 100	341 ms	355320 KiB

kas

#include "bits/stdc++.h"
using namespace std;
#define intt int
#define fi first
#define se second

const intt mxN = 1e5;
const intt LG = 20;
const intt inf = 1e18;  

intt n;
vector<vector<intt>> dp;
vector<intt> a;

void _() {
    cin >> n;
    a.resize(n);
    dp.assign(n + 1, vector<intt>(2 * mxN+10));
    intt sum = 0;
    for(intt i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(intt j = 0; j <= 2 * mxN; j++) {
        dp[0][j] = -inf;
    }
    dp[0][mxN]=0;

    for(intt i = 1; i < n; i++) {
        for(intt j = 0; j <= 2 * mxN; j++) {
            dp[i][j] = dp[i-1][j];
            if(j + a[i] <= 2 * mxN) {
                dp[i][j] = max(dp[i][j], dp[i-1][j + a[i]] + a[i]);
            }
            if(j - a[i] >= 0) {
                dp[i][j] = max(dp[i][j], dp[i-1][j - a[i]] + a[i]);
            }
        }
    }
    intt ans = 0;
    for(intt i = 0; i < n; i++) ans += a[i];
    cout << ans - dp[n-1][mxN] / 2 << endl;
}
//complete edu

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cout.tie(NULL);
    
    intt t = 1, buu = 1;
    // cin >> t;
    while(t--){
        // cout << "Case #" << buu++ << ": ";
        _();
    }
}

Compilation message (stderr)

kas.cpp:9:18: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    9 | const intt inf = 1e18;
      |                  ^~~~

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