oj.uz

Submission #99166

# Submission time Handle Problem Language Result Execution time Memory
99166 2019-03-01T11:37:49 Z dalgerok Kas (COCI17_kas) C++17
100 / 100
 710 ms 198180 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 198008 KB Output is correct
2 Correct 154 ms 198040 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 197984 KB Output is correct
2 Correct 151 ms 198080 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 198004 KB Output is correct
2 Correct 155 ms 198008 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 198096 KB Output is correct
2 Correct 156 ms 198008 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 197968 KB Output is correct
2 Correct 163 ms 198008 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 198052 KB Output is correct
2 Correct 161 ms 197936 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 197948 KB Output is correct
2 Correct 153 ms 198008 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 197960 KB Output is correct
2 Correct 175 ms 198008 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 198064 KB Output is correct
2 Correct 268 ms 198008 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 397 ms 198136 KB Output is correct
2 Correct 710 ms 198180 KB Output is correct