답안 #41098

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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]);
                          ^
# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 398856 KB Output is correct
2 Correct 291 ms 398956 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 398956 KB Output is correct
2 Correct 290 ms 398956 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 295 ms 399056 KB Output is correct
2 Correct 288 ms 399276 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 288 ms 399276 KB Output is correct
2 Correct 292 ms 399288 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 399288 KB Output is correct
2 Correct 292 ms 399288 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 298 ms 399288 KB Output is correct
2 Correct 298 ms 399288 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 309 ms 399288 KB Output is correct
2 Correct 324 ms 399288 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 450 ms 399288 KB Output is correct
2 Correct 325 ms 399288 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 473 ms 399356 KB Output is correct
2 Correct 478 ms 399356 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 694 ms 399356 KB Output is correct
2 Correct 1167 ms 399356 KB Output is correct