oj.uz

Submission #170513

# Submission time Handle Problem Language Result Execution time Memory
170513 2019-12-25T14:35:44 Z mdn2002 Kas (COCI17_kas) C++14
100 / 100
 1262 ms 391928 KB 
#include<bits/stdc++.h>
using namespace std;
const long long mod=998244353;
int n,a[503],dp[500][200000],al;
int f(int x,int sum)
{
    if(x==n)
    {
        if(sum==1e5)return 0;
        else return -1e5;
    }
    if(dp[x][sum]!=-1)return dp[x][sum];
    int num=-1e5;
    num=max(num,f(x+1,sum+a[x])+a[x]);
    num=max(num,f(x+1,sum-a[x]));
    num=max(num,f(x+1,sum));
    return dp[x][sum]=num;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("lemonade.in","r",stdin);
    //freopen("lemonade.out","w",stdout);
    memset(dp,-1,sizeof dp);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        al+=a[i];
    }
    cout<<f(0,1e5)+((al-(f(0,1e5)*2)));
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 391928 KB Output is correct
2 Correct 323 ms 391800 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 391792 KB Output is correct
2 Correct 329 ms 391772 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 391780 KB Output is correct
2 Correct 322 ms 391800 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 391744 KB Output is correct
2 Correct 325 ms 391672 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 391700 KB Output is correct
2 Correct 400 ms 391792 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 391672 KB Output is correct
2 Correct 369 ms 391680 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 391768 KB Output is correct
2 Correct 550 ms 391800 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 742 ms 391800 KB Output is correct
2 Correct 1262 ms 391792 KB Output is correct