結果

問題 No.974 最後の日までに
ユーザー shibh308shibh308
提出日時 2019-12-09 16:19:04
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,773 bytes
コンパイル時間 2,205 ms
コンパイル使用メモリ 206,428 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-25 16:50:33
合計ジャッジ時間 80,787 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 1,489 ms
6,944 KB
testcase_18 AC 1,487 ms
6,940 KB
testcase_19 AC 1,487 ms
6,944 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 AC 1,487 ms
6,940 KB
testcase_30 WA -
testcase_31 AC 2 ms
6,944 KB
testcase_32 AC 1,487 ms
6,940 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 AC 1,488 ms
6,940 KB
testcase_36 AC 1,488 ms
6,944 KB
testcase_37 WA -
testcase_38 AC 1,494 ms
6,940 KB
testcase_39 AC 1,488 ms
6,940 KB
testcase_40 WA -
testcase_41 AC 1,486 ms
6,944 KB
testcase_42 WA -
testcase_43 WA -
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 AC 1,488 ms
6,944 KB
testcase_50 AC 1,487 ms
6,940 KB
testcase_51 AC 1,487 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

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, money_n_scale;

unsigned long xor128(void)
{
    static unsigned long x=123456789,y=362436069,z=521288629,w=88675123;
    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_scale * money : money_scale * money) + val_scale * 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_scale = 10;
    money_scale = 100;
    money_n_scale = 1;

    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 = (1.0 * accumulate(a.begin(), a.end(), 0L) + accumulate(c.begin(), c.end(), 0L));
    val_scale = accumulate(b.begin(), b.end(), 0L);
    i64 ans = 0;
    i64 money = accumulate(a.begin(), a.end(), 0L);
    i64 val = 0;
    i64 s = 0;

    double per;
    while((per = (double(clock() - st) / CLOCKS_PER_SEC) / 1.48) < 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