oj.uz

답안 #965467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
965467 2024-04-18T16:44:10 Z phamducminh Kas (COCI17_kas) C++17
100 / 100
 248 ms 399020 KB 
//******************/
//*   I<3   C++    */
//*  I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S long longERESTING*/
//* I LOVE PROGRAM!*/
//*  IN CONTESTS   */
//*   GET SCORE    */
//*    AC CODE     */
//*     LET'S      */
//*      GO        */
//*  Written by:   */
//*   Duc Minh     */






#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <string>
#include <queue>
#include <cctype>
#include <cstring>
#include <iomanip>
#include <deque>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define  file(name)  freopen(name".inp", "r", stdin);\
                     freopen(name".out", "w", stdout);
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define TIME        (1.0 * clock() / CLOCKS_PER_SEC)
#define all(a)      a.begin(),a.end()
#define endl        "\n"
#define all1(a)     a+1,a+n+1
#define unordered_map  map
// #define push_back   emplace_back
// #define gcd(a,b)    __gcd(a,b);
// #define lcm(a,b)    (a*b)/gcd(a,b);

const long long INF = (long long)1e9;
const long long MOD = (long long)1e9+7;
const long long MODD = 1e9; /// 998244353
const int maxN = 1e5+55;
const int LOG = 30;
const int mlift = 20;







///--------------------------------


void solve();

signed main(){

    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);



    // file("CTREE");







    long long t;


    // cin >> t;

    t=1;



    while (t--){




        solve();


    }





    cerr << "Time elapsed: " << TIME << "s.\n";
    cerr << "ducminh" << "\n";
    return 0;
}



///--------------------[PROBLEM SOLUTION]--------------------///



long long dp[509][100009];
long long sum=0,n,a[509];

void solve(){


    // dp[i][sum]

    cin >> n;

    for (int i=1; i<=n; i++){
        cin >> a[i];
        sum+=a[i];
    }

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;


    for (int i=1; i<=n; i++){
        for (int j=0; j<=sum; j++){
            if (j+a[i]<=sum) dp[i][j]=min(dp[i][j],dp[i-1][j+a[i]]);
            dp[i][j]=min({dp[i][j],dp[i-1][j]+a[i],dp[i-1][abs(j-a[i])]});
        }
    }


    cout << (sum-dp[n][0])/2+dp[n][0];



}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 203 ms 398740 KB Output is correct
2 Correct 119 ms 399020 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 398848 KB Output is correct
2 Correct 117 ms 398852 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 398676 KB Output is correct
2 Correct 116 ms 398672 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 398676 KB Output is correct
2 Correct 116 ms 398912 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 398916 KB Output is correct
2 Correct 116 ms 398752 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 115 ms 398696 KB Output is correct
2 Correct 116 ms 398768 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 398784 KB Output is correct
2 Correct 118 ms 398676 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 192 ms 398908 KB Output is correct
2 Correct 165 ms 398664 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 398900 KB Output is correct
2 Correct 205 ms 398908 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 248 ms 398816 KB Output is correct
2 Correct 224 ms 398904 KB Output is correct