oj.uz

Submission #100209

# Submission time Handle Problem Language Result Execution time Memory
100209 2019-03-09T20:06:44 Z Leonardo_Paes Kas (COCI17_kas) C++11
100 / 100
 1299 ms 400120 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 399916 KB Output is correct
2 Correct 316 ms 399992 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 399916 KB Output is correct
2 Correct 331 ms 400028 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 399972 KB Output is correct
2 Correct 326 ms 399992 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 399964 KB Output is correct
2 Correct 324 ms 399992 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 400012 KB Output is correct
2 Correct 308 ms 399928 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 334 ms 399888 KB Output is correct
2 Correct 309 ms 400008 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 400120 KB Output is correct
2 Correct 323 ms 400068 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 399904 KB Output is correct
2 Correct 350 ms 400120 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 487 ms 399992 KB Output is correct
2 Correct 563 ms 400044 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 744 ms 399988 KB Output is correct
2 Correct 1299 ms 399988 KB Output is correct