/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 520.0 KiB
#2 Accepted 2ms 568.0 KiB
#3 Accepted 2ms 484.0 KiB
#4 Accepted 22ms 1.227 MiB
#5 Accepted 4ms 616.0 KiB
#6 Accepted 22ms 1.117 MiB
#7 Accepted 14ms 880.0 KiB
#8 Accepted 18ms 796.0 KiB
#9 Accepted 25ms 1.285 MiB
#10 Accepted 28ms 1.004 MiB
#11 Accepted 26ms 1.289 MiB
#12 Accepted 16ms 776.0 KiB
#13 Accepted 29ms 1.309 MiB
#14 Accepted 33ms 1.316 MiB
#15 Accepted 28ms 1.23 MiB
#16 Accepted 28ms 1.082 MiB
#17 Accepted 28ms 1.32 MiB
#18 Accepted 28ms 1.188 MiB
#19 Accepted 28ms 1.324 MiB
#20 Accepted 29ms 1.277 MiB
#21 Accepted 23ms 1.07 MiB
#22 Accepted 23ms 1.027 MiB
#23 Accepted 29ms 1.309 MiB
#24 Accepted 22ms 1.223 MiB
#25 Accepted 28ms 1.277 MiB
#26 Accepted 2ms 328.0 KiB
#27 Accepted 2ms 328.0 KiB

Code

#include <bits/stdc++.h>
typedef long long     ll;
#define endl          '\n'
#define F             first
#define S             second
#define pb            push_back
#define yes           cout<<"YES\n"
#define no            cout<<"NO\n"
#define all(x)        x.begin(),x.end()
#define allr(x)       x.rbegin(),x.rend()
#define CheckBit(x,k) (x & (1LL << k))
#define SetBit(x,k)   (x |= (1LL << k))
#define ClearBit(x,k) (x &= ~(1LL << k))
#define MSB(mask)     63-__builtin_clzll(mask) 
#define LSB(mask)     __builtin_ctzll(mask)  
#define error1(x)     cerr << #x << " = " << (x) <<endl
#define error2(a,b)   cerr<<"("<<#a<<", "<<#b<<") = ("<<(a)<<", "<<(b)<<")\n";
#define coutall(v)    for(auto &it: v) cout<<it<<" "; cout<<endl;
#define _ASRafi__     ios::sync_with_stdio(false); cin.tie(0);
using namespace std;

void solve()
{
    ll n, k, ans = 0;
    cin >> n >> k;
    vector<bitset<41>> v(n);
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        v[i] = x;
    }
    vector<pair<ll, ll>> profit(41);
    for(int i = 0; i < 41; i++) {
        ll c1 = 0;
        for(int j = 0; j < n; j++) c1 += v[j][i];
        // if x[i] = 1
        ll lab = (n - c1) * (1LL << i), loss = c1 * (1LL << i);
        profit[i] = {lab, loss};
        // cout << i << " -> " << lab << ", " << loss << endl;
    }
    bitset<41> b1 = k;
    bool ok = 0;
    for(int i = 40; i >= 0; i--) { // sob nibo
        if(ok) ans += max(profit[i].F, profit[i].S);
        else if(profit[i].F <= profit[i].S){
            ans += max(profit[i].F, profit[i].S);
            if(b1[i] == 1) ok = 1;
        }
        else if(b1[i] == 1) ans += profit[i].F;
        else ans += profit[i].S;
        // cout << i << " => " << ans << endl;
    }   

    ll back = 0;
    for(int i = 40; i >= 0; i--) { // nibo na
        if(b1[i] == 1) {
            ll tmp = back + profit[i].S;
            for(int j = i - 1; j >= 0; j--) {
                tmp += max(profit[j].F, profit[j].S);
            }
            ans = max(ans, tmp);
        }

        if(b1[i] == 1) back += max(profit[i].F, profit[i].S);
        else back += profit[i].S;
    }
    cout << ans << endl;
    return;
}

int32_t main()
{
    _ASRafi__;
    int tc = 1;
    // cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        // cout << "Case " << t << ": ";
        solve();
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1054 Yet another challenge for Roy!
Language
C++20 (G++ 13.2.0)
Submit At
2024-05-06 20:29:10
Judged At
2024-11-11 03:31:28
Judged By
Score
100
Total Time
33ms
Peak Memory
1.324 MiB