Submission #93106

#	Time	Username	Problem	Language	Result	Execution time	Memory
93106		Ahmad_Elsisy	Kas (COCI17_kas)	C++14	100 / 100	505 ms	198136 KiB

kas

#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define popcnt(x) __builtin_popcount(x)
#define inf 0x3f3f3f3f
#define watch(x) cout << (#x) << " is " << (x) << endl

using namespace std;
typedef long long  ll;
const int N = 505 , M = 1e5 + 4;
int n , memo[N][M];
vector<int> a;

int solve(int indx , int s){
    if(indx == n){
        return (!s ? 0 : -inf);
    }

    int &ret = memo[indx][s];
    if(~ret)
        return ret;

    ret = -inf;
    ret = max(ret , a[indx] + solve(indx + 1 , s + a[indx]));
    ret = max(ret , max(0, a[indx] - s) + solve(indx + 1 , abs(s - a[indx])));
    ret = max(ret , solve(indx + 1 , s));
    return ret;
}
int main() {
    ios::sync_with_stdio() , cin.tie(0) , cin.tie(0);
    int tot = 0;
    cin >> n;
    a.resize(n);
    for(int &x : a)
        cin >> x , tot += x;
    memset(memo , -1 , sizeof memo);
    int v = solve(0 , 0);
    cout << v + (tot - 2 * v) << '\n';
}

• 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