oj.uz

Submission #922217

# Submission time Handle Problem Language Result Execution time Memory
922217 2024-02-05T08:50:55 Z Whisper Kas (COCI17_kas) C++17
100 / 100
 395 ms 395860 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 395712 KB Output is correct
2 Correct 152 ms 395752 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 395560 KB Output is correct
2 Correct 162 ms 395572 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 395672 KB Output is correct
2 Correct 146 ms 395668 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 395652 KB Output is correct
2 Correct 135 ms 395576 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 395604 KB Output is correct
2 Correct 135 ms 395720 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 395516 KB Output is correct
2 Correct 143 ms 395860 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 395740 KB Output is correct
2 Correct 138 ms 395596 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 395764 KB Output is correct
2 Correct 152 ms 395756 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 395588 KB Output is correct
2 Correct 182 ms 395660 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 395604 KB Output is correct
2 Correct 395 ms 395800 KB Output is correct