Submission #922217

#	Time	Username	Problem	Language	Result	Execution time	Memory
922217		Whisper	Kas (COCI17_kas)	C++17	100 / 100	395 ms	395860 KiB

kas

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using str = string;
using T = tuple<ll, ll, ll>;

#define int long long
#define Base 41
#define sz(a) (int)a.size()
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for ( int i = b ; i >= a ; i-- )
#define REP(i, n) for ( int i = 0 ; i < n ; ++i )
#define REPD(i, n) for ( int i =  n - 1 ; ~(--i) ; )
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)
constexpr ll MN = 1e6 + 1;

constexpr ll LINF = (1ll << 62);
constexpr int INF = (1ll << 31);
constexpr int MAX = 5e2 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

void setupIO( const string& PROB ){

    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    // freopen( (PROB + ".inp").c_str(), "r", stdin);
    // freopen( (PROB + ".out").c_str(), "w", stdout);
    cout << fixed << setprecision(10);
}

int n;
int a[MAX];

const int maxN = 1e5 + 5;


int dp[MAX][maxN];


//dp(i, diff) is the total money with difference diff till i

int f(int i , int diff){
    if (i == n + 1) return (diff == 0 ? 0 : -INF);
    if (diff >= (int)(1e6)) return -INF;

    int &ans = dp[i][diff];
    if (~ans) return ans;
    ans = max({f(i + 1, diff), f(i + 1, diff + a[i]) + a[i], f(i + 1, abs(diff - a[i])) + a[i]});

    return ans;
}
void Whisper(){
    cin >> n;
    for (int i = 1 ; i <= n ; i++) cin >> a[i];
    int sum = accumulate(a + 1, a + n + 1, 0ll);
    memset(dp, -1, sizeof dp);
    
    int ans = f(0, 0) / 2 + sum - f(0, 0);

    cout << ans;
}            

signed main(){  
    setupIO("Whisper");
    int Test = 1;
    // cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\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