oj.uz

Submission #655141

# Submission time Handle Problem Language Result Execution time Memory
655141 2022-11-03T08:55:57 Z prvocislo Uplifting Excursion (BOI22_vault) C++17
0 / 100
 188 ms 3208 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<ll> dp(z * 2 + 5, -inf); // dp[layer][zero + sucet oproti povodnemu greedy]
void upd(ll& a, ll b)
{
    a = max(a, b);
}
void apply(ll siz, ll cost)
{
    if (siz > 0)
    {
        for (ll j = z - siz; j >= -z; j--) if (dp[z + j] != -inf) upd(dp[z + j + siz], dp[z + j] + cost);
    }
    else
    {
        for (ll j = -z - siz; j <= z; j++) if (dp[z + j] != -inf) upd(dp[z + j + siz], dp[z + j] + cost);
    }
}
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;
    }
    int ly = 0;
    dp[z] = cnt;
    for (ll i = -m; i <= m; i++)
    {
        vector<ll> jump;
        ll neg = min(g[m + i], 2ll * m);
        if (neg > 0)
        {
            for (ll j = 1; j <= neg; j <<= 1ll) if (j - 1 <= neg) jump.push_back(j), neg -= j;
            jump.push_back(neg);
            for (ll j : jump) apply(j * -i, -j);
        }
        ll pos = min(a[m + i] - g[m + i], 2ll * m);
        if (pos > 0)
        {
            for (ll j = 1; j <= pos; j <<= 1ll) if (j - 1 <= pos) jump.push_back(j), pos -= j;
            jump.push_back(pos);
            for (ll j : jump) apply(j * i, j);
        }
    }
    ll d = l - sum;
    if (d > (ll)z || dp[z + d] == -inf) cout << "impossible\n";
    else cout << dp[z + d] << "\n";
    return 0;
}

Compilation message

vault.cpp: In function 'int main()':
vault.cpp:62:9: warning: unused variable 'ly' [-Wunused-variable]
   62 |     int ly = 0;
      |         ^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3156 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 5 ms 3156 KB Output is correct
4 Correct 14 ms 3156 KB Output is correct
5 Incorrect 188 ms 3156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3156 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 5 ms 3156 KB Output is correct
4 Correct 14 ms 3156 KB Output is correct
5 Incorrect 188 ms 3156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3208 KB Output is correct
2 Correct 46 ms 3156 KB Output is correct
3 Incorrect 20 ms 3156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3208 KB Output is correct
2 Correct 46 ms 3156 KB Output is correct
3 Incorrect 20 ms 3156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3208 KB Output is correct
2 Correct 46 ms 3156 KB Output is correct
3 Incorrect 20 ms 3156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3156 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 5 ms 3156 KB Output is correct
4 Correct 14 ms 3156 KB Output is correct
5 Incorrect 188 ms 3156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3208 KB Output is correct
2 Correct 46 ms 3156 KB Output is correct
3 Incorrect 20 ms 3156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3156 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 5 ms 3156 KB Output is correct
4 Correct 14 ms 3156 KB Output is correct
5 Incorrect 188 ms 3156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3208 KB Output is correct
2 Correct 46 ms 3156 KB Output is correct
3 Incorrect 20 ms 3156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3156 KB Output is correct
2 Correct 4 ms 3156 KB Output is correct
3 Correct 5 ms 3156 KB Output is correct
4 Correct 14 ms 3156 KB Output is correct
5 Incorrect 188 ms 3156 KB Output isn't correct
6 Halted 0 ms 0 KB -