제출 #335545

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

biscuits

#include "biscuits.h"
 
#include <cassert>
 
typedef long long int64_t;

// O(Q * K^2)-time solution
int64_t count_tastiness(int64_t numGroups, std::vector<int64_t> initialCount) {
    while (initialCount.size() < 62) initialCount.push_back(0);
    int64_t spareCount = 0;
    auto numWays = std::vector<int64_t>{1};
    for (int64_t i = 0; i < static_cast<int64_t>(initialCount.size()); ++i) {
        if (initialCount[i] + spareCount >= numGroups) {
            spareCount = spareCount + initialCount[i] - numGroups;
            assert(spareCount >= 0);
            numWays.push_back(numWays.back() * 2);
        } else {
            int64_t maxPossible = 0;
            int64_t availableQty = 0;
            for (int64_t j = 0; j <= i; ++j) {
                availableQty += initialCount[j] << j;
            }
            int64_t borrowedQty = 0;
            for (int64_t j = i; j >= 0; --j) {
                assert(availableQty >= borrowedQty);
                assert((borrowedQty % (1LL << j)) == 0);
                int64_t curCount = initialCount[j];
                int64_t returnedQty = std::min(borrowedQty, curCount << j);
                curCount -= returnedQty >> j;
                availableQty -= returnedQty;
                borrowedQty -= returnedQty;
                assert(curCount >= 0 && curCount <= initialCount[j]);
                if (((availableQty - borrowedQty) >> j) >= numGroups) {
                    borrowedQty += numGroups << j;
                    borrowedQty = std::max(0LL, borrowedQty - (curCount << j));
                    maxPossible |= 1LL << j;
                }
                availableQty -= curCount << j;
            }
            assert(borrowedQty == 0);
            int64_t curWays = 0;
            for (int64_t j = 0; j < i + 1; ++j) {
                if (((maxPossible + 1) & (1LL << j)) > 0) curWays += numWays[j];
            }
            numWays.push_back(curWays);
            spareCount = 0;
        }
        spareCount >>= 1LL;
    }
    return numWays.back();
}
 

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