oj.uz

Submission #655124

# Submission time Handle Problem Language Result Execution time Memory
655124 2022-11-03T07:31:44 Z prvocislo Uplifting Excursion (BOI22_vault) C++17
0 / 100
 107 ms 12188 KB 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <deque>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 305;
const ll inf = 1e18 + 5, z = 2 * maxn * maxn;
int m;
ll l;
vector<ll> a(maxn * 2 + 5);
vector<ll> g(maxn * 2 + 5); // volba pazraveho riesenia
ll cnt = 0;
vector<vector<ll> > dp(2, vector<ll>(z * 2 + 5, -inf)); // dp[layer][zero + sucet oproti povodnemu greedy]
void upd(ll& a, ll b)
{
    a = max(a, b);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m >> l;
    ll sum = 0;
    for (ll i = -m; i <= m; i++) cin >> a[m + i], sum += a[m + i] * i;
    if (sum < l)
    {
        l *= -1ll;
        reverse(a.begin(), a.begin() + 2 * m + 1);
    }
    // l < sum -> v greedy rieseni zoberieme vsetky zaporne a nejaky prefix kladnych
    sum = 0;
    for (ll i = -m; i <= m; i++)
    {
        ll k = min(a[m + i], (i <= 0 ? inf : (l - sum) / i));
        g[m + i] += k, sum += k * i, cnt += k;
    }
    vector<ll> tr;
    for (int i = 0; (1 << i) <= 2 * m; i++) tr.push_back((1 << i)), tr.push_back(-(1 << i));
    int ly = 0;
    dp[0][z] = cnt;
    for (ll i = -m; i <= m; i++)
    {
        dp[ly ^ 1] = dp[ly];
        for (ll sum = -z; sum <= z; sum++) if (dp[ly][z + sum] != -inf)
        {
            ll neg = g[m + i];
            if (i < 0) neg = min(neg, (z + sum) / (-i));
            if (i > 0) neg = min(neg, (z - sum) / i);
            vector<ll> jump;
            for (ll j = 2; j <= neg; j <<= 1ll) if (j - 1 <= neg) jump.push_back(j - 1), neg -= j - 1;
            jump.push_back(neg);
            for (ll j : jump) upd(dp[ly ^ 1][z + sum - j * i], dp[ly][z + sum] - j);
            ll pos = min(a[m + i] - g[m + i], 2ll * m);
            if (i > 0) pos = min(pos, (z + sum) / i);
            if (i < 0) pos = min(pos, (z - sum) / (-i));
            jump.clear();
            for (ll j = 2; j <= pos; j <<= 1ll) if (j - 1 <= pos) jump.push_back(j - 1), pos -= j - 1;
            jump.push_back(pos);
            for (ll j : jump) upd(dp[ly ^ 1][z + sum + j * i], dp[ly][z + sum] + j);
        }
        ly ^= 1;
    }
    ll d = l - sum;
    if (d > (ll)z || dp[ly][z + d] == -inf) cout << "impossible\n";
    else cout << dp[ly][z + d] << "\n";
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9044 KB Output is correct
2 Correct 10 ms 8984 KB Output is correct
3 Correct 6 ms 9048 KB Output is correct
4 Correct 14 ms 9044 KB Output is correct
5 Runtime error 107 ms 12184 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9044 KB Output is correct
2 Correct 10 ms 8984 KB Output is correct
3 Correct 6 ms 9048 KB Output is correct
4 Correct 14 ms 9044 KB Output is correct
5 Runtime error 107 ms 12184 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9044 KB Output is correct
2 Runtime error 27 ms 12188 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9044 KB Output is correct
2 Runtime error 27 ms 12188 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9044 KB Output is correct
2 Runtime error 27 ms 12188 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9044 KB Output is correct
2 Correct 10 ms 8984 KB Output is correct
3 Correct 6 ms 9048 KB Output is correct
4 Correct 14 ms 9044 KB Output is correct
5 Runtime error 107 ms 12184 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9044 KB Output is correct
2 Runtime error 27 ms 12188 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9044 KB Output is correct
2 Correct 10 ms 8984 KB Output is correct
3 Correct 6 ms 9048 KB Output is correct
4 Correct 14 ms 9044 KB Output is correct
5 Runtime error 107 ms 12184 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 9044 KB Output is correct
2 Runtime error 27 ms 12188 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9044 KB Output is correct
2 Correct 10 ms 8984 KB Output is correct
3 Correct 6 ms 9048 KB Output is correct
4 Correct 14 ms 9044 KB Output is correct
5 Runtime error 107 ms 12184 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -