Submission #100207

#	Time	Username	Problem	Language	Result	Execution time	Memory
100207		Leonardo_Paes	Kas (COCI17_kas)	C++11	100 / 100	1463 ms	400248 KiB

kas

#include <bits/stdc++.h>

using namespace std;

#define MAXN 510
#define MAXM 100100

int n, sum, vet[MAXN], dp[MAXN][2*MAXM], prefsum[MAXN];

int solve(int pos, int val){
    if(pos==n+1 and val!=100000)return 0x3f3f3f3f;
    if(pos==n+1){
        return 0;
    }
    if(dp[pos][val]!=-1)return dp[pos][val];

    int caso1 = solve(pos+1, val);
    int caso2 = solve(pos+1, val+vet[pos]);
    int caso3 = solve(pos+1, val-vet[pos]);

    if(caso1!=0x3f3f3f3f) caso1+=vet[pos];

    int menor = min(min(caso1, caso2),caso3);

    if(val==100000)menor=min(menor, sum-prefsum[pos-1]);

    return dp[pos][val]=menor;
}

int main(){

    cin >> n;

    for(int i=1; i<=n; i++){
        cin >> vet[i];
        prefsum[i]=vet[i]+prefsum[i-1];
        sum+=vet[i];
    }

    memset(dp, -1, sizeof dp);

    int ans = solve(0, 100000);

    cout << (sum-ans)/2 + ans << endl;
}

• 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