제출 #428322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
428322		Peti	비스킷 담기 (IOI20_biscuits)	C++14	0 / 100	45 ms	332 KiB

biscuits

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

using namespace std;

const int bitc = 60;

vector<long long> ossz, dp;
long long suti;

long long ert = 0;
void megold(int x, vector<long long> v){
    if(x == -1){
        ert += (long long)v.size();
        return;
    }
    vector<long long> v2;
    long long db = 0;
    for(long long y : v){
        if((1ll<<x)*suti <= y){
            v2.push_back(y-(1ll<<x)*suti);
            db++;
        }else
            v2.push_back(y);
    }

    ert += dp[x]*db;
    megold(x-1, v2);
}

long long count_tastiness(long long x, std::vector<long long> a) {
    suti = x;
    ossz.assign(bitc, 0);
    dp.assign(bitc, 0);
    ossz[0] = a[0];
    for(int i = 1; i < (int)a.size(); i++)
        ossz[i] = ossz[i-1] + (1ll<<i)*a[i];
    for(int i = (int)a.size(); i < bitc; i++)
        ossz[i] = ossz[i-1];

    for(int i = 0; i < bitc; i++){
        if(i > 0)
            dp[i] = dp[i-1];
        ert = 0;
        if(ossz[i] >= (1ll<<i)*suti)
            megold(i-1, {ossz[i] - (1ll<<i)*suti});
        dp[i] += ert;
    }

	return dp[bitc-1]+1ll;
}

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