oj.uz

Submission #947238

# Submission time Handle Problem Language Result Execution time Memory
947238 2024-03-15T18:25:19 Z tmarcinkevicius Uplifting Excursion (BOI22_vault) C++14
0 / 100
 313 ms 524288 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 287 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 287 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 313 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 313 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 313 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 287 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 313 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 287 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 313 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Runtime error 287 ms 524288 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -