Submission #425658

#	Time	Username	Problem	Language	Result	Execution time	Memory
425658		idk321	Packing Biscuits (IOI20_biscuits)	C++17	21 / 100	1165 ms	1142460 KiB

biscuits

#include "biscuits.h"
#include <bits/stdc++.h>;
using namespace std;
typedef long long ll;


long long count_tastiness(long long x, std::vector<long long> a) {
    ll sum = 0;
    int k = 60;
    for (int i = 0; i < a.size(); i++)
    {
        sum += (1LL << i) * a[i];
    }




    if (sum <= 100000)
    {
        int res = 0;

        for (int i = 0; i <= sum; i++)
        {
            bool poss = true;
            vector<ll> cur(60);
            for (int j = 0; j < a.size(); j++) cur[j] = a[j];
            for (int j = 0; j < k; j++)
            {
                if ((1LL << j) & i)
                {
                    cur[j] -= x;

                    if (cur[j] < 0)
                    {
                        poss = false;
                        break;
                    }
                }


                if (j + 1 < k)
                {
                    cur[j + 1] += cur[j] / 2;
                }
            }


            if (poss) res++;
        }

        return res;
    }


    a.resize(k);
    for (int i = 0; i < k - 1; i++)
    {
        if (a[i] - (x + 2) >= 0)
        {
            ll diff = (a[i] - (x + 2));
            a[i + 1] += diff / 2;
            a[i] -= (diff / 2) * 2;
        }
    }

    vector<vector<ll>> dp(k + 1, vector<ll>(x * k * 2));
    dp[k][0] = 1;
    for (int i = k - 1;i >= 0; i--)
    {

        for (int j = 0; (j + a[i]) / 2 < x * k * 2 && j < x * k * 2; j++)
        {

            if (j + a[i] < x)
            {
                dp[i][j] = dp[i + 1][(j + a[i]) / 2];
            } else
            {
                dp[i][j] = dp[i + 1][(j + a[i]) / 2] + dp[i + 1][(j + a[i] - x) / 2];
            }
        }
    }



    return dp[0][0];
}

/*
1
15 1
1 2 0 2 1 0 0 2 2 1 1 2 0 0 1
*/

Compilation message (stderr)

biscuits.cpp:2:25: warning: extra tokens at end of #include directive
    2 | #include <bits/stdc++.h>;
      |                         ^
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
biscuits.cpp:26:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             for (int j = 0; j < a.size(); j++) cur[j] = a[j];
      |                             ~~^~~~~~~~~~

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