oj.uz

Submission #676175

# Submission time Handle Problem Language Result Execution time Memory
676175 2022-12-29T16:13:18 Z Ahmed57 Kas (COCI17_kas) C++14
100 / 100
 641 ms 391704 KB 
#include<bits/stdc++.h>
using namespace std;
int arr[500];int n;
int dp[500][200001];
int solve(int i,int sum){
    if(i==n){
        if(sum==100000)return 0;
        else return -1e9;
    }
    if(dp[i][sum]!=-1)return dp[i][sum];
    return dp[i][sum] = max({solve(i+1,sum),solve(i+1,sum-arr[i]),solve(i+1,sum+arr[i])+arr[i]});
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n;int sum = 0;
    for(int i = 0;i<n;i++){cin>>arr[i];sum+=arr[i];}
    memset(dp,-1,sizeof dp);
    cout<<solve(0,100000)+((sum-(2*solve(0,100000))));
}
//

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 391592 KB Output is correct
2 Correct 142 ms 391588 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 391576 KB Output is correct
2 Correct 143 ms 391668 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 391628 KB Output is correct
2 Correct 141 ms 391648 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 391668 KB Output is correct
2 Correct 140 ms 391672 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 391676 KB Output is correct
2 Correct 146 ms 391680 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 391576 KB Output is correct
2 Correct 141 ms 391596 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 391628 KB Output is correct
2 Correct 142 ms 391588 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 391704 KB Output is correct
2 Correct 169 ms 391644 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 391616 KB Output is correct
2 Correct 264 ms 391632 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 391628 KB Output is correct
2 Correct 641 ms 391656 KB Output is correct