제출 #1032732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032732		12345678	Packing Biscuits (IOI20_biscuits)	C++17	21 / 100	1068 ms	600 KiB

biscuits

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

using namespace std;

#define ll long long

ll n=70, dp[3][70];

long long count_tastiness2(long long x, std::vector<long long> a) {
    ll sm=0, k=min(17ll, (ll)a.size()), res=0;
    for (int i=0; i<k; i++) sm+=(1<<i)*a[i];
    for (int y=1; y*x<=sm; y++)
    {
        vector<ll> cnt=a;
        for (int t=0; t<x; t++)
        {
            ll tmp=y, vl;
            for (int i=k-1; i>=0; i--)
            {
                if ((1<<i)>tmp) continue;
                if ((1<<i)*cnt[i]<=tmp) tmp-=(1<<i)*cnt[i], cnt[i]=0;
                else vl=tmp/(1<<i), tmp-=(1<<i)*vl, cnt[i]-=vl;
            }
            if (tmp!=0) break;
            if (t==x-1) res++;
        }
    }
    return res+1;
}

long long count_tastiness(long long x, std::vector<long long> a) {
    if (x!=1) return count_tastiness2(x, a);
    ll k=a.size();
    vector<ll> cnt(70);
    for (int i=0; i<k; i++) cnt[i]=a[i];
    for (int i=0; i<70; i++) dp[0][i]=dp[1][i]=dp[2][i]=0;
    for (int i=0; i<70; i++) if (cnt[i]>2) cnt[i+1]+=(cnt[i]-1)/2, cnt[i]-=2*((cnt[i]-1)/2);
    //for (int i=0; i<10; i++) cout<<i<<' '<<cnt[i]<<'\n';
    for (int i=0; i<70; i++)
    {
        if (i==0) for (int j=0; j<=cnt[i]; j++) dp[j][i]=1;
        else
        {
            if (cnt[i]==0) dp[0][i]=dp[0][i-1]+dp[1][i-1]+dp[2][i-1];
            else if (cnt[i]==1) dp[0][i]=dp[0][i-1]+dp[1][i-1], dp[1][i]=dp[0][i-1]+dp[1][i-1], dp[2][i]=dp[2][i-1];
            else dp[0][i]=dp[0][i-1]+dp[1][i-1], dp[1][i]=dp[0][i-1]+dp[1][i-1], dp[2][i]=dp[0][i-1]+dp[1][i-1]+dp[2][i-1];
        }
        //cout<<"debug "<<i<<' '<<dp[0][i]<<' '<<dp[1][i]<<' '<<dp[2][i]<<'\n';
    }
    return dp[0][69]+dp[1][69]+dp[2][69];
}

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