Submission #975070

#	Time	Username	Problem	Language	Result	Execution time	Memory
975070		LucaIlie	비스킷 담기 (IOI20_biscuits)	C++17	9 / 100	1075 ms	646380 KiB

biscuits

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

using namespace std;

const int k = 60;
long long x;
long long biscuits[k];
__int128 sum[k];
vector<long long> sol;

long long count_tastiness( long long X, vector <long long> a ) {
    long long s;

    x = X;
    a.resize( k );

    s = 0;
    for ( int b = 0; b < k; b++ ) {
        a[b] += s;
        if ( a[b] > x ) {
            s = a[b] - x;
            a[b] = x + s % 2;
            s /= 2;
        } else
            s = 0;
        biscuits[b] = a[b];
    }

    sum[0] = biscuits[0];
    for ( int b = 1; b < k; b++ )
        sum[b] = sum[b - 1] + ((__int128)biscuits[b] << b);

    sol.clear();
    sol.push_back( 0 );
    for ( int b = 0; b < k; b++ ) {
        vector<long long> newSol;
        for ( long long y: sol ) {
            if ( y + (1LL << b) <= sum[b] / x )
                newSol.push_back( y + (1LL << b) );
            else
                break;
        }
        for ( int y: newSol )
            sol.push_back( y );
    }

    return sol.size();
}

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