oj.uz

Submission #182407

# Submission time Handle Problem Language Result Execution time Memory
182407 2020-01-09T18:00:50 Z XmtosX Kas (COCI17_kas) C++17
100 / 100
 1317 ms 395000 KB 
#include <bits/stdc++.h>
using namespace std;
const int N=504;
int n,memo[N][200005],a[N];
int dp (int pos,int cur)
{
    if (pos==n)
    {
        if (cur==1e5)
            return 0;
        return 1e9;
    }
    int &ret=memo[pos][cur];
    if (ret!=-1)
        return ret;
    ret=dp(pos+1,cur)+a[pos];
    ret=min(ret,dp(pos+1,cur-a[pos]));
    ret=min(ret,dp(pos+1,cur+a[pos]));
    return ret;
}
int main()
{
    int sum=0;
    cin >>n;
    for (int i=0;i<n;i++)
        cin >>a[i],sum+=a[i];
    memset(memo,-1,sizeof memo);
    int ans= dp(0,1e5);
    cout <<ans+ (sum-ans)/2;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 394872 KB Output is correct
2 Correct 329 ms 394880 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 394892 KB Output is correct
2 Correct 331 ms 394872 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 394976 KB Output is correct
2 Correct 331 ms 394844 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 394872 KB Output is correct
2 Correct 333 ms 394836 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 394904 KB Output is correct
2 Correct 332 ms 394812 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 394880 KB Output is correct
2 Correct 329 ms 394876 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 394804 KB Output is correct
2 Correct 330 ms 394844 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 395000 KB Output is correct
2 Correct 392 ms 394844 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 394976 KB Output is correct
2 Correct 588 ms 394864 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 395000 KB Output is correct
2 Correct 1317 ms 394912 KB Output is correct