Submission #1072941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072941		Ignut	Packing Biscuits (IOI20_biscuits)	C++17	33 / 100	28 ms	44020 KiB

biscuits

// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll dp[123][22222];

ll count_tastiness(ll x, vector<ll> a) {
    int k = a.size();
    for (int i = 0; i < k; i ++) {
        if (a[i] > x) {
            if (i == a.size() - 1) {
                a.push_back(0);
                k ++;
            }
            ll del = a[i] - x;
            if (del % 2 == 1) del --;
            a[i + 1] += del / 2;
            a[i] -= del;
        }
    }
    a.push_back(0);
    k ++;

    // for (int val : a) cerr << val << ' ';
    // cout << '\n';

    int lim = 2 * x + 2;

    for (int i = 0; i <= k; i ++)
        for (int v = 0; v <= lim; v ++)
            dp[i][v] = 0;

    dp[0][0] = 1;
    for (int i = 0; i < k; i ++) {
        for (int prev = 0; prev <= lim; prev ++) {
            ll val = a[i] + prev / 2;
            val = min(val, 1ll * lim);
            // take 1
            if (val >= x)
                dp[i + 1][val - x] += dp[i][prev];
            // take 0
            dp[i + 1][val] += dp[i][prev];
        }
    }

    // for (int i = 0; i <= k; i ++) {
    //     for (int v = 0; v <= 3; v ++) {
    //         cout << dp[i][v] << ' ';
    //     }
    //     cout << '\n';
    // }

    ll res = 0;
    for (int v = 0; v <= lim; v ++) res += dp[k][v];
    return res;
}

Compilation message (stderr)

biscuits.cpp: In function 'll count_tastiness(ll, std::vector<long long int>)':
biscuits.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |             if (i == a.size() - 1) {
      |                 ~~^~~~~~~~~~~~~~~

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