제출 #1065905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1065905		vjudge1	비스킷 담기 (IOI20_biscuits)	C++17	100 / 100	14 ms	1372 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vll = vector<ll>;
using i128 = __int128;

ll count_tastiness(ll x, vll a) {
    int n = int(a.size());
    int MN = 63;
    vll C(MN, 0);
    for(int i = 0; i < MN; ++i) {
        if(i < n) C[i] = a[i] * (1ll << i);
        if(i) C[i] += C[i - 1];
    }
    for(int i = 0; i < MN; ++i) 
        C[i] /= x;

    vll F(MN, 0);
    F[0] = 1;

    function<ll(int, ll)> taie = [&](int k, ll lim) -> ll {
        if(lim < 0) return 0ll;
        if(lim >= (1ll << k) - 1) return F[k];
        //k > 0 de aici
        lim = min(lim, C[k - 1]);
        ll mij = (1ll << (k - 1)) - 1;
        if(lim <= mij) return taie(k - 1, lim);
        return taie(k - 1, lim - mij - 1) + F[k - 1];
    };
    for(int i = 1; i < MN; ++i) {
        F[i] = F[i - 1] + taie(i - 1, C[i - 1] - (1ll << (i - 1)));
    }
	return F.back();
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 21 / 21
• Subtask 4: 35 / 35
• Subtask 5: 23 / 23