提出 #48429828

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;
using i128 = __int128_t;
#define rep(i,n) for(i64 i=0; i<(i64)(n); i++)
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    i64 INF = 0x3FFF'FFFF'FFFF'FFFF;
    
    i64 N, D; cin >> N >> D;
    vector<i64> W(N);
    rep(i,N) cin >> W[i];
    vector<i64> A(1<<N);
    rep(d,N) rep(i,1<<d) A[i+(1<<d)] = A[i] + W[d];
    i64 s = A[(1<<N)-1];
    rep(i,1<<N) A[i] = A[i] * A[i];
    auto dp = vector<i64>(1<<N, INF);
    dp[(1<<N)-1] = 0;
    i64 mindp = INF;
    rep(d,D){
        rep(i,1<<(N-d)){
            int rem = (1<<(N-d)) - 1 - i;
            for(int j=rem; j>0; j=(j-1)&rem){
                chmin(dp[i], dp[i+j] + A[j]);
            }
        }
        chmin(mindp, dp[0]);
    }
    cout.precision(20);
    cout << fixed;
    double ans = double((i128)mindp * D - (i128)s * s) / D / D;
    cout << ans << endl;
    return 0;
}

提出情報

提出日時
問題 E - Lucky bag
ユーザ Nachia
言語 C++ 20 (gcc 12.2)
得点 525
コード長 1065 Byte
結果 AC
実行時間 25 ms
メモリ 3964 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 525 / 525
結果
AC × 1
AC × 57
セット名 テストケース
Sample example_00.txt
All example_00.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, random_35.txt, random_36.txt, random_37.txt, random_38.txt, random_39.txt, random_40.txt, random_41.txt, random_42.txt, random_43.txt, random_44.txt, random_45.txt, random_46.txt, random_47.txt, random_48.txt, random_49.txt
ケース名 結果 実行時間 メモリ
example_00.txt AC 2 ms 3736 KiB
hand_00.txt AC 24 ms 3884 KiB
hand_01.txt AC 24 ms 3796 KiB
hand_02.txt AC 24 ms 3848 KiB
hand_03.txt AC 1 ms 3756 KiB
hand_04.txt AC 1 ms 3756 KiB
hand_05.txt AC 24 ms 3772 KiB
random_00.txt AC 8 ms 3716 KiB
random_01.txt AC 22 ms 3776 KiB
random_02.txt AC 9 ms 3764 KiB
random_03.txt AC 23 ms 3816 KiB
random_04.txt AC 9 ms 3768 KiB
random_05.txt AC 25 ms 3792 KiB
random_06.txt AC 9 ms 3772 KiB
random_07.txt AC 25 ms 3824 KiB
random_08.txt AC 9 ms 3752 KiB
random_09.txt AC 25 ms 3960 KiB
random_10.txt AC 9 ms 3748 KiB
random_11.txt AC 24 ms 3700 KiB
random_12.txt AC 9 ms 3840 KiB
random_13.txt AC 24 ms 3804 KiB
random_14.txt AC 9 ms 3768 KiB
random_15.txt AC 25 ms 3804 KiB
random_16.txt AC 9 ms 3716 KiB
random_17.txt AC 25 ms 3780 KiB
random_18.txt AC 9 ms 3772 KiB
random_19.txt AC 25 ms 3796 KiB
random_20.txt AC 25 ms 3696 KiB
random_21.txt AC 24 ms 3756 KiB
random_22.txt AC 25 ms 3804 KiB
random_23.txt AC 25 ms 3888 KiB
random_24.txt AC 25 ms 3780 KiB
random_25.txt AC 24 ms 3816 KiB
random_26.txt AC 25 ms 3820 KiB
random_27.txt AC 25 ms 3816 KiB
random_28.txt AC 25 ms 3780 KiB
random_29.txt AC 25 ms 3884 KiB
random_30.txt AC 25 ms 3880 KiB
random_31.txt AC 25 ms 3780 KiB
random_32.txt AC 25 ms 3780 KiB
random_33.txt AC 25 ms 3816 KiB
random_34.txt AC 25 ms 3956 KiB
random_35.txt AC 25 ms 3808 KiB
random_36.txt AC 24 ms 3780 KiB
random_37.txt AC 25 ms 3964 KiB
random_38.txt AC 9 ms 3748 KiB
random_39.txt AC 9 ms 3780 KiB
random_40.txt AC 9 ms 3772 KiB
random_41.txt AC 9 ms 3768 KiB
random_42.txt AC 9 ms 3772 KiB
random_43.txt AC 9 ms 3748 KiB
random_44.txt AC 9 ms 3776 KiB
random_45.txt AC 25 ms 3820 KiB
random_46.txt AC 4 ms 3912 KiB
random_47.txt AC 2 ms 3756 KiB
random_48.txt AC 25 ms 3812 KiB
random_49.txt AC 9 ms 3752 KiB