oj.uz

Submission #694131

# Submission time Handle Problem Language Result Execution time Memory
694131 2023-02-03T21:34:21 Z finn__ Uplifting Excursion (BOI22_vault) C++17
20 / 100
 15 ms 456 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx2")

int main()
{
    int64_t m, l;
    cin >> m >> l;

    vector<int64_t> a(2 * m + 1);
    for (int64_t &x : a)
        cin >> x;

    if (l < 0)
    {
        l = -l;
        for (int64_t i = 0; i < m; i++)
            swap(a[m - i - 1], a[m + i + 1]);
    }

    int64_t p = 0, total_added = 0;
    vector<int64_t> b(a.begin(), a.end());
    for (int64_t i = -m; i <= 0; i++)
        p += a[i + m] * i, b[i + m] = 0, total_added += a[i + m];
    for (int64_t i = 1; i <= m; i++)
    {
        for (int64_t j = 62; j >= 0; j--)
            if (1LL << j <= b[i + m] && p + (1LL << j) * i <= l)
            {
                p += (1LL << j) * i;
                b[i + m] -= 1LL << j;
                total_added += 1LL << j;
            }
    }

    if (p < l - m)
    {
        p = 0;
        total_added = 0;
        b = vector<int64_t>(a.begin(), a.end());
        for (int64_t i = 0; i <= m; i++)
            p += a[i + m] * i, b[i + m] = 0, total_added += a[i + m];
        for (int64_t i = -1; i >= -m; i--)
        {
            for (int64_t j = 62; j >= 0; j--)
                if (1LL << j <= b[i + m] && p + (1LL << j) * i >= l)
                {
                    p += (1LL << j) * i;
                    b[i + m] -= 1LL << j;
                    total_added += 1LL << j;
                }
        }

        if (p < l - m)
        {
            cout << "impossible\n";
            return 0;
        }
    }

    // l resides at m * m.
    vector<int64_t> dp1(2 * m * m + 1, 0), dp2(2 * m * m + 1, 0);
    dp1[m * m - (l - p)] = total_added;

    for (int64_t i = -m; i <= m; i++)
    {
        vector<int64_t> max_add(dp1.size(), min<int64_t>(b[i + m], m)),
            max_remove = vector<int64_t>(dp1.size(), min<int64_t>(a[i + m] - b[i + m], m));

        bool f = 1;

        for (int64_t k = 0; f; k++)
        {
            f = 0;
            for (int64_t j = 0; j < dp1.size(); j++)
            {
                if (!dp1[j] || !(0 <= j + (1LL << k) * i && j + (1LL << k) * i < dp1.size() && 1LL << k < max_add[j]))
                    continue;
                f = 1;
                dp2[j + (1LL << k) * i] = max<int64_t>(dp2[j + (1LL << k) * i], dp1[j] + (1LL << k));
                max_add[j] -= 1LL << k;
            }

            swap(dp1, dp2);
            for (size_t i = 0; i < dp1.size(); i++)
                dp1[i] = max(dp1[i], dp2[i]), dp2[i] = max(dp1[i], dp2[i]);
        }

        for (int64_t j = 0; j < dp1.size(); j++)
            if (dp1[j] && 0 <= j + max_add[j] * i && j + max_add[j] * i < dp1.size())
                dp2[j + max_add[j] * i] = max<int64_t>(dp2[j + max_add[j] * i], dp1[j] + max_add[j]);

        swap(dp1, dp2);
        for (size_t i = 0; i < dp1.size(); i++)
            dp1[i] = max(dp1[i], dp2[i]), dp2[i] = max(dp1[i], dp2[i]);

        f = 1;

        for (int64_t k = 0; f; k++)
        {
            f = 0;
            for (int64_t j = 0; j < dp1.size(); j++)
            {
                if (!dp1[j] || !(0 <= j - (1LL << k) * i && j - (1LL << k) * i < dp1.size() && 1LL << k < max_remove[j]))
                    continue;
                f = 1;
                dp2[j - (1LL << k) * i] = max<int64_t>(dp2[j - (1LL << k) * i], dp1[j] - (1LL << k));
                max_remove[j] -= 1LL << k;
            }

            swap(dp1, dp2);
            for (size_t i = 0; i < dp1.size(); i++)
                dp1[i] = max(dp1[i], dp2[i]), dp2[i] = max(dp1[i], dp2[i]);
        }

        for (int64_t j = 0; j < dp1.size(); j++)
            if (dp1[j] && 0 <= j - max_remove[j] * i && j - max_remove[j] * i < dp1.size())
                dp2[j - max_remove[j] * i] = max<int64_t>(dp2[j - max_remove[j] * i], dp1[j] - max_remove[j]);

        swap(dp1, dp2);
        for (size_t i = 0; i < dp1.size(); i++)
            dp1[i] = max(dp1[i], dp2[i]), dp2[i] = max(dp1[i], dp2[i]);
    }

    if (!dp1[m * m])
        cout << "impossible\n";
    else
        cout << dp1[m * m] << '\n';
}

Compilation message

vault.cpp: In function 'int main()':
vault.cpp:77:35: 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 (int64_t j = 0; j < dp1.size(); j++)
      |                                 ~~^~~~~~~~~~~~
vault.cpp:79:80: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |                 if (!dp1[j] || !(0 <= j + (1LL << k) * i && j + (1LL << k) * i < dp1.size() && 1LL << k < max_add[j]))
      |                                                             ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
vault.cpp:91:31: 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]
   91 |         for (int64_t j = 0; j < dp1.size(); j++)
      |                             ~~^~~~~~~~~~~~
vault.cpp:92:73: 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]
   92 |             if (dp1[j] && 0 <= j + max_add[j] * i && j + max_add[j] * i < dp1.size())
      |                                                      ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
vault.cpp:104:35: 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]
  104 |             for (int64_t j = 0; j < dp1.size(); j++)
      |                                 ~~^~~~~~~~~~~~
vault.cpp:106:80: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                 if (!dp1[j] || !(0 <= j - (1LL << k) * i && j - (1LL << k) * i < dp1.size() && 1LL << k < max_remove[j]))
      |                                                             ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
vault.cpp:118:31: 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]
  118 |         for (int64_t j = 0; j < dp1.size(); j++)
      |                             ~~^~~~~~~~~~~~
vault.cpp:119:79: 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]
  119 |             if (dp1[j] && 0 <= j - max_remove[j] * i && j - max_remove[j] * i < dp1.size())
      |                                                         ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 15 ms 456 KB Output is correct
7 Correct 8 ms 456 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 15 ms 452 KB Output is correct
10 Incorrect 5 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 15 ms 456 KB Output is correct
7 Correct 8 ms 456 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 15 ms 452 KB Output is correct
10 Incorrect 5 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3-1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct

Subtask #3-2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 2 ms 340 KB Output is correct
24 Correct 3 ms 340 KB Output is correct
25 Correct 2 ms 340 KB Output is correct
26 Correct 3 ms 340 KB Output is correct
27 Correct 3 ms 340 KB Output is correct
28 Correct 3 ms 340 KB Output is correct

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Incorrect 4 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 15 ms 456 KB Output is correct
7 Correct 8 ms 456 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 15 ms 452 KB Output is correct
10 Incorrect 5 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Incorrect 4 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 15 ms 456 KB Output is correct
7 Correct 8 ms 456 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 15 ms 452 KB Output is correct
10 Incorrect 5 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 2 ms 340 KB Output is correct
19 Correct 2 ms 340 KB Output is correct
20 Correct 2 ms 340 KB Output is correct
21 Incorrect 4 ms 340 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 15 ms 456 KB Output is correct
7 Correct 8 ms 456 KB Output is correct
8 Correct 14 ms 340 KB Output is correct
9 Correct 15 ms 452 KB Output is correct
10 Incorrect 5 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -