Submission #1191009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191009		peteza	Kas (COCI17_kas)	C++20	100 / 100	212 ms	2464 KiB

kas

#include <bits/stdc++.h>
using namespace std;

const int add = 120000;
int n, arr[505];
int sm, dp[250005], old[250005];

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n;
    for(int i=0;i<=250004;i++) old[i] = -9999999;
    old[add] = 0;
    for(int k=1;k<=n;k++) {
        cin >> arr[k];
        sm += arr[k];
        for(int i=0;i<=250004;i++) dp[i] = old[i];
        for(int i=0;i<=250004;i++) {
            if(i+arr[k] <= 250004) dp[i+arr[k]] = max(old[i], dp[i+arr[k]]);
            if(i-arr[k] >= 0) dp[i-arr[k]] = max(old[i] + arr[k], dp[i-arr[k]]);
        }
        for(int i=0;i<=250004;i++) old[i] = dp[i];
        //for(int i=add-20;i<=add+20;i++) cout << old[i] << ' ' ; cout << '\n';
    }
    cout << sm - old[add];
}

• 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