Submission #1256211

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256211		nanaseyuzuki	Kas (COCI17_kas)	C++20	100 / 100	533 ms	395788 KiB

kas

#include <bits/stdc++.h>
/*
    --> Author: Kazuki_Hoshino__8703 <--
    I love Nanasaki Ai ☆*: .。. o(≒＿≒)o .。.:☆
*/
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair <int, int>

const int mn = 505, inf = 1e17, mm = 1e5 + 5;

int m, n, q;
int a[mn], dp[mn][mm];

int f(int i, int diff){
    if(i == n + 1){
        if(diff == 0) return 0;
        return -inf;   
    }
    if(dp[i][diff] != -1) return dp[i][diff];
    dp[i][diff] = max({a[i] + f(i + 1, diff + a[i]), a[i] + f(i + 1, abs(diff - a[i])), f(i + 1, diff)});
    // cout << i << ' ' << diff << ' ' << dp[i][diff] << '\n';
    return dp[i][diff];
}

void solve(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
    }
    memset(dp, -1, sizeof(dp));
    int qq = f(1, 0);
    cout << qq / 2 + (sum - qq) << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10