Submission #1017016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017016		dimashhh	Packing Biscuits (IOI20_biscuits)	C++17	9 / 100	1060 ms	4184 KiB

biscuits

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 1;
int ok[N];
int n,timer = 0;
int hsb(ll x)
{
    for(int i = 60;i >= 0;i--){
        if((x >> i) & 1){
            return i;
        }
    }
    return -1;
}
ll s[N];
int b = 19;
ll count_tastiness(ll x, vector<ll> a){
    ++timer;
    n = (int)a.size();
    for(int i = 0;i <= b;i++){
        s[i] = 0;
    }
    for(int i = 0;i < n;i++){
        s[i] = (1ll << i) * 1ll * a[i];
    }
    for(int i =1;i <= b;i++){
        s[i] += s[i - 1];
    }
    ok[0] = timer;
    int ret = 0;
    // cout << x << ' ' << n << "f\n";
    for(int i = 0;i < N;i++){
        if(ok[i] == timer){
            ret++;
            int t = hsb(i);
            for(int j = t + 1;j <= b;j++){
                ll left = s[j] - i * 1ll * x;
                if(left / x >= (1ll << j) * 1ll){
                    if((i | (1ll << j)) > N) return -1;
                    ok[(i | (1ll << j))] = timer;
                }
            }
        }
    }
    return ret;
}

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