oj.uz

Submission #100210

# Submission time Handle Problem Language Result Execution time Memory
100210 2019-03-09T20:08:16 Z Leonardo_Paes Kas (COCI17_kas) C++11
100 / 100
 1373 ms 400168 KB 
#include <bits/stdc++.h>

using namespace std;

#define MAXN 510
#define MAXM 100100

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

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);

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

int main(){

    cin >> n;

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

    memset(dp, -1, sizeof dp);

    int ans = solve(0, 100000);

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 399992 KB Output is correct
2 Correct 291 ms 399864 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 400000 KB Output is correct
2 Correct 290 ms 399864 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 399936 KB Output is correct
2 Correct 314 ms 399920 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 294 ms 399992 KB Output is correct
2 Correct 293 ms 400040 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 399896 KB Output is correct
2 Correct 300 ms 399900 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 399864 KB Output is correct
2 Correct 316 ms 399896 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 399876 KB Output is correct
2 Correct 303 ms 399864 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 400028 KB Output is correct
2 Correct 362 ms 399864 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 492 ms 399992 KB Output is correct
2 Correct 567 ms 400168 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 400060 KB Output is correct
2 Correct 1373 ms 400120 KB Output is correct