oj.uz

Submission #41098

# Submission time Handle Problem Language Result Execution time Memory
41098 2018-02-12T16:46:37 Z Hassoony Kas (COCI17_kas) C++14
100 / 100
 1167 ms 399356 KB 
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef double D;
typedef long long ll;
typedef pair<int,int> pii;
const ll mod=1e9+7;
const int inf=(1<<30);
const int SQ=1e6+9;
const int MX=509;
int n,a[MX],dp[MX][100000*2+9],sum;
int DP(int x,int y){
    if(x==n){
        if(y==100000)return 0;
        return -inf;
    }
    int &ret=dp[x][y];if(ret!=-1)return ret;
    ret=DP(x+1,y);
    ret=max(ret,DP(x+1,y+a[x])+a[x]);
    ret=max(ret,DP(x+1,y-a[x]));
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    memset(dp,-1,sizeof(dp));
    cout<<sum-DP(0,100000)<<endl;
}

Compilation message

kas.cpp: In function 'int main()':
kas.cpp:24:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
kas.cpp:26:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 398856 KB Output is correct
2 Correct 291 ms 398956 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 398956 KB Output is correct
2 Correct 290 ms 398956 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 399056 KB Output is correct
2 Correct 288 ms 399276 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 399276 KB Output is correct
2 Correct 292 ms 399288 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 399288 KB Output is correct
2 Correct 292 ms 399288 KB Output is correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 399288 KB Output is correct
2 Correct 324 ms 399288 KB Output is correct

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 399356 KB Output is correct
2 Correct 478 ms 399356 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 694 ms 399356 KB Output is correct
2 Correct 1167 ms 399356 KB Output is correct