Submission #99166

#	Time	Username	Problem	Language	Result	Execution time	Memory
99166		dalgerok	Kas (COCI17_kas)	C++17	100 / 100	710 ms	198180 KiB

kas

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


const int N = 505, M = 1e5 + 5, INF = 1e9;



int n, sum, a[N], dp[N][M];

int rec(int pos, int val){
    if(val > sum){
        return -INF;
    }
    int &cur = dp[pos][val];
    if(cur != -1){
        return cur;
    }
    if(pos == n + 1){
        return cur = (val != 0) * -INF;
    }
    return cur = max({rec(pos + 1, val), rec(pos + 1, val + a[pos]) + a[pos], rec(pos + 1, abs(val - a[pos])) + max(0, a[pos] - val)});
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
    }
    memset(dp, -1, sizeof(dp));
    cout << sum - rec(0, 0);
}

• 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