Submission #1070760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070760		andrei_iorgulescu	Packing Biscuits (IOI20_biscuits)	C++14	0 / 100	1080 ms	495072 KiB

biscuits

#include <bits/stdc++.h>
#include "biscuits.h"
#warning That's not FB, that's my FB

using namespace std;

#define int long long

int count_tastiness(int x, vector<int> a)
{
    vector<int> sp(60);
    while (a.size() < 60)
        a.push_back(0);
    sp[0] = a[0];
    for (int i = 1; i < 60; i++)
        sp[i] = sp[i - 1] + (1ll << i) * a[i];
    for (int i = 0; i < 60; i++)
        sp[i] /= x;
    vector<vector<int>> dp(60);
    vector<vector<int>> s(60);
    for (int i = 59; i >= 0; i--)
    {
        s[i].push_back(sp[i]);
        sort(s[i].begin(), s[i].end());
        vector<int> ns;
        for (auto it : s[i])
            if (ns.empty() or it != ns.back())
                ns.push_back(it);
        s[i] = ns;
        dp[i].resize(s[i].size());
        if (i == 0)
            continue;
        for (auto it : s[i])
        {
            if (it - (1ll << i) >= 0 and it - (1ll << i) < sp[i - 1])
                s[i - 1].push_back(it - (1ll << i));
            if (it < sp[i - 1])
                s[i - 1].push_back(it);
        }
    }
    for (int j = 0; j < dp[0].size(); j++)
        dp[0][j] = 1 + s[0][j];
    for (int i = 1; i < 60; i++)
    {
        int pant = -1, pant2 = -1;
        for (int j = 0; j < dp[i].size(); j++)
        {
            while (pant + 1 < s[i - 1].size() and s[i][j] - (1ll << i) >= s[i - 1][pant + 1])
                pant++;
            while (pant2 + 1 < s[i - 1].size() and s[i][j] >= s[i - 1][pant2 + 1])
                pant2++;
            if (pant != -1)
                dp[i][j] += dp[i - 1][pant];
            if (pant2 != -1)
                dp[i][j] += dp[i - 1][pant2];
        }
    }
    return dp[59].back();
}

Compilation message (stderr)

biscuits.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~
biscuits.cpp: In function 'long long int count_tastiness(long long int, std::vector<long long int>)':
biscuits.cpp:41:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int j = 0; j < dp[0].size(); j++)
      |                     ~~^~~~~~~~~~~~~~
biscuits.cpp:46:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (int j = 0; j < dp[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~
biscuits.cpp:48:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             while (pant + 1 < s[i - 1].size() and s[i][j] - (1ll << i) >= s[i - 1][pant + 1])
      |                    ~~~~~~~~~^~~~~~~~~~~~~~~~~
biscuits.cpp:50:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             while (pant2 + 1 < s[i - 1].size() and s[i][j] >= s[i - 1][pant2 + 1])
      |                    ~~~~~~~~~~^~~~~~~~~~~~~~~~~

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