Submission #309704

#	Time	Username	Problem	Language	Result	Execution time	Memory
309704		georgerapeanu	Packing Biscuits (IOI20_biscuits)	C++17	42 / 100	1088 ms	16484 KiB

biscuits

#include "biscuits.h"
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int maxK = 128;

long long count_tastiness(long long x, vector<long long> a) {

    unordered_map<long long,long long> mp;

    mp[0] = 1;

    while(a.size() < maxK){
        a.push_back(0);
    }

    for(int i = 0;i < maxK - 1;i++){
        if(a[i] >= x){
            a[i + 1] += (a[i] - x) / 2;
            a[i] -= ((a[i] - x) / 2) * 2;
        }
    }

    for(int i = 0;i < (int)a.size();i++){
        unordered_map<long long,long long> tmp;
        for(auto it2:mp){
            pair<long long,long long> it = it2;
            it.first += a[i];
            tmp[it.first / 2] += it.second;
            if(it.first >= x){
                tmp[(it.first - x) / 2] += it.second;
            }
        }
        mp = tmp;
    }

	return mp[0];
}

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