Submission #1289805

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289805		mariaclara	Packing Biscuits (IOI20_biscuits)	C++17	44 / 100	113 ms	2496 KiB

biscuits

#include "biscuits.h"
#include<vector>
using namespace std;

typedef long long ll;
#define sz(x) (int)x.size()
#define pb push_back

ll pos[(int)2e5+1];

ll count_tastiness(ll x, vector<ll> a) {
    ll s[60], pot;
    int i, j;
    s[0] = a[0];

    for(i = 1, pot = 2; i < 60; i++, pot *= 2) {
        s[i] = s[i-1];
        if(i < sz(a)) s[i] += pot * a[i];
    }

    int SZ = 1, new_SZ = 1;
    pos[0] = 0;

    for(i = 0, pot = 1; i < 60; i++, pot *= 2, SZ = new_SZ) {
        for(j = 0; j < SZ; j++) {
            // se s[i] >= x(pos[j]+pot)
            if(s[i]/x < pos[j]+pot) break;
            pos[new_SZ] = pos[j] + pot;
            new_SZ++;
        }
    }

    return SZ;
}

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