Submission #947238

#	Time	Username	Problem	Language	Result	Execution time	Memory
947238		tmarcinkevicius	Uplifting Excursion (BOI22_vault)	C++14	0 / 100	313 ms	524288 KiB

vault

#include <bits/stdc++.h>  
using namespace std;

#define int int64_t
typedef pair<int,int> pii;
typedef vector<int> vii;
#define MP make_pair
#define PB push_back
#define f first
#define s second
#define INF 2e18
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())

int M, L;

int32_t main()
{
    fast_io();

    cin >> M >> L;
    vector<int> values;
    values.push_back(0);
    int offset = 0;
    int maxVal = 0;

    for (int val = -M; val <= M; val++)
    {
        int x;
        cin >> x;
        for (int i = 0; i < x; i++)
        {
            values.push_back(val);
            if (val > 0)
            {
                maxVal += val;
            }
            else
            {
                offset -= val;
            }
        }
    }

    if (L > maxVal)
    {
        cout << "impossible\n";
        return 0;
    }

    /*cout << "values: {";
    for (int i : values)
    {
        cout << i << " ";
    }
    cout << "}\n";*/

    offset *= 2;

    //cout << "L = " << L << ", offset = " << offset << ", maxVal = " << maxVal << '\n';
    //return 0;
    int sizeY = offset + maxVal;

    int dp[values.size()][sizeY];

    for (int i = 0; i < values.size(); i++)
    {
        for (int j = 0; j < sizeY; j++)
        {
            dp[i][j] = -INF;
        }
    }

    dp[0][offset] = 0;

    for (int i = 1; i < values.size(); i++)
    {
        for (int l = -offset; offset + l < sizeY; l++)
        {
            //cout << "realVal: " << l << '\n';
            dp[i][offset + l] = dp[i - 1][offset + l];

            if (offset + l - values[i] >= 0 && offset + l - values[i] < sizeY)
            {
                dp[i][offset + l] = max(dp[i][offset + l], dp[i - 1][offset + l - values[i]] + 1);
            }
        }
    }

    /*for (int l = -L; l <= L; l++)
    {
        cout << setw(5) << l << " ";
    }
    cout << '\n';
    for (int i = 0; i < values.size(); i++)
    {
        for (int l = -L; l <= L; l++)
        {
            if (dp[i][offset + L] < -INF / 2)
            {
                cout << setw(5) << "-";
            }
            else
            {
                cout << setw(5) << dp[i][offset + L];
            }
            cout << " ";
        }
        cout << '\n';
    }*/

    if (dp[values.size() - 1][offset + L] <= 0)
    {
        cout << "impossible\n";
    }
    else
    {
        cout << dp[values.size() - 1][offset + L] << '\n';
    }
    
}

Compilation message (stderr)

vault.cpp: In function 'int32_t main()':
vault.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < values.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
vault.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 1; i < values.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3-1: 0 / 10
• Subtask 3-2: 0 / 10
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 10
• Subtask 5-2: 0 / 10
• Subtask 6-1: 0 / 10
• Subtask 6-2: 0 / 10