結果

問題 No.974 最後の日までに
ユーザー shibh308
提出日時 2019-12-09 17:18:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,714 bytes
コンパイル時間 2,517 ms
コンパイル使用メモリ 198,216 KB
最終ジャッジ日時 2025-01-08 10:15:34
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 WA * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"

using namespace std;

using i64 = long long;

const i64 MOD = 1000000007;


double startt = 10;
double endt = 1;

double val_scale, money_scale;
double val_p, money_p, money_n_p, tim;

unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
unsigned long xor128(void)
{
    unsigned long t;
    t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) );
}

double score(i64 _money, i64 _val){
    double money = _money / money_scale;
    double val = _val / val_scale;
    return (money < 0 ? money_n_p * money : money_p * money) + val_p * val;
}

bool go(double temp, i64 bef_money, i64 bef_val, i64 aft_money, i64 aft_val){
    double per = exp((score(aft_money, aft_val) - score(bef_money, bef_val)) / (startt + (endt - startt) * temp));
    bool ret = (1.0 * xor128() / numeric_limits<unsigned long>::max()) < per;
    return ret;
}

signed main(){

    ifstream o("val.txt", ios::in);
    val_p = 99913;
    money_p = 0.8;
    money_n_p = 23879;
    endt = 4753;
    startt = 92153;
    tim = 1.48;

    clock_t st = clock();
    int n;
    cin >> n;
    vector<i64> a(n), b(n), c(n);
    for(int i = 0; i < n; ++i)
        cin >> a[i] >> b[i] >> c[i];
    if(n == 1){
        cout << 0 << endl;
        return 0;
    }

    a.emplace_back(0);
    b.emplace_back(0);
    c.emplace_back(0);
    a.emplace_back(0);
    b.emplace_back(0);
    c.emplace_back(0);
    money_scale = accumulate(a.begin(), a.end(), 0L) + accumulate(c.begin(), c.end(), 0L);
    money_scale /= 2 * n;
    val_scale = accumulate(b.begin(), b.end(), 0L);
    val_scale /= n;
    i64 ans = 0;
    i64 money = accumulate(a.begin(), a.end(), 0L);
    i64 val = 0;
    i64 s = 0;

    double per;

    for(int i = 0; i < n / 4; ++i){
        int idx = xor128() % (n - 1);

        i64 nex_money = money;
        i64 nex_val = val;
        i64 t = s;
        if(!((t >> idx) & 1)){
            // turn on
            t |= (1LL << idx);

            // natural
            if((t >> (idx + 1)) & 1){
                t &= ~(1LL << (idx + 1));
                nex_money += a[idx + 1];
                nex_money += a[idx + 2];
                nex_money += c[idx + 2];
                nex_val -= b[idx + 2];
            }

            nex_money -= a[idx];
            nex_money -= a[idx + 1];
            nex_money -= c[idx + 1];
            nex_val += b[idx + 1];

        }
        else{
            continue;
        }

        if(nex_money >= 0)
            ans = max(ans, nex_val);
        s = t;
        money = nex_money;
        val = nex_val;
    }

    while((per = (double(clock() - st) / CLOCKS_PER_SEC) / tim) < 1){
        int idx = xor128() % (n - 1);

        i64 nex_money = money;
        i64 nex_val = val;
        i64 t = s;
        if(!((t >> idx) & 1)){
            // turn on
            t |= (1LL << idx);

            // natural
            if((t >> (idx + 1)) & 1){
                t &= ~(1LL << (idx + 1));
                nex_money += a[idx + 1];
                nex_money += a[idx + 2];
                nex_money += c[idx + 2];
                nex_val -= b[idx + 2];
            }

            nex_money -= a[idx];
            nex_money -= a[idx + 1];
            nex_money -= c[idx + 1];
            nex_val += b[idx + 1];

        }
        else{
            t &= ~(1LL << idx);
            nex_money += a[idx];
            nex_val -= b[idx + 1];
            nex_money += a[idx + 1];
            nex_money += c[idx + 1];
        }

        if(nex_money >= 0){
            ans = max(ans, nex_val);
        }
        if(go(per, money, val, nex_money, nex_val)){
            s = t;
            money = nex_money;
            val = nex_val;
        }
    }
    cout << ans << endl;
}
0