제출 #1217109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217109		user736482	Packing Biscuits (IOI20_biscuits)	C++20	100 / 100	10 ms	972 KiB

biscuits

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 1000000009
#define INF 1000000019
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
ll count_tastiness(ll x,vector<ll>a){
    while(a.size()!=60)a.pb(0);
    ll k=a.size();
    ll dp[k+1][k+1];
    for(ll i=0;i<=k;i++)for(ll j=0;j<=k;j++)dp[i][j]=(i==0);
    for(ll i=1;i<k;i++)a[i]=(a[i]<<i)+a[i-1];
    for(ll i=0;i<k;i++){a[i]/=x;a[i]=min(a[i],((1LL<<(i+1))-1));
    }
    ll pom[k+1];
    for(ll i=0;i<=k;i++)pom[i]=(1LL<<i)-1;
    for(ll i=1;i<=k;i++){
        if(a[i-1] &( 1LL<<(i-1)))
        dp[i][0]=dp[i-1][0];
        dp[i][0]+=dp[i-1][i];
        for(ll j=i+1;j<=k;j++){
            if((a[j-1] & pom[i]) > (a[i-1] & pom[i]))
                dp[i][j]+=dp[i-1][i];
            else
                dp[i][j]+=dp[i-1][j];
            if((a[j-1] & (1LL<<(i-1)))&&(a[i-1] & (1LL<<(i-1)))){
                if(a[i-1] & (1LL<<(i-1)))
                    dp[i][j]+=dp[i-1][0];
                else
                    dp[i][j]+=dp[i-1][i];
                
            }
            
        }
    }
    return dp[k][0];
}

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