oj.uz

Submission #943714

# Submission time Handle Problem Language Result Execution time Memory
943714 2024-03-11T18:35:26 Z LucaIlie Uplifting Excursion (BOI22_vault) C++17
10 / 100
 5000 ms 18424 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_M = 300;
const int MAX_S = MAX_M * MAX_M;
const int MIN_S = -MAX_S;
const long long INF = 1e18;
int m;
unordered_map<int, long long> taken, untaken;
unordered_map<int, long long> dpCrt, dpPrv;

void add( int x, int i ) {
    swap( dpCrt, dpPrv );

    for ( int s = MIN_S; s <= MAX_S; s++ )
        dpCrt[s] = dpPrv[s];

    for ( int s = MIN_S; s - i * x <= MAX_S; s++ ) {
        if ( MIN_S <= s - i * x && s - i * x <= MAX_S )
            dpCrt[s] = max( dpCrt[s], dpPrv[s - i * x] + x );
    }

    for ( int s = MIN_S; s <= MAX_S; s++ )
        dpCrt[s] = (dpCrt[s] <= -INF + m ? -INF : dpCrt[s]);
}

void substract( int x, int i ) {
    swap( dpCrt, dpPrv );

    for ( int s = MIN_S; s <= MAX_S; s++ )
        dpCrt[s] = dpPrv[s];

    for ( int s = MIN_S; s <= MAX_S; s++ ) {
        if ( MIN_S <= s + i * x && s + i * x <= MAX_S )
            dpCrt[s] = max( dpCrt[s], dpPrv[s + i * x] - x );
    }

    for ( int s = MIN_S; s <= MAX_S; s++ )
        dpCrt[s] = (dpCrt[s] <= -INF + m ? -INF : dpCrt[s]);
}

void afis() {
    for ( int s = MIN_S; s <= MAX_S; s++ )
        cout << dpCrt[s] << " ";
    cout << "\n";
}

int main() {
    long long l, u = 0, t = 0;

    cin >> m >> l;
    for ( int i = -m; i <= m; i++ ) {
        cin >> untaken[i];
        u += untaken[i];
    }

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

    long long s = 0;
    for ( int i = -m; i <= 0; i++ ) {
        long long x = untaken[i];
        s += i * x;
        taken[i] += x;
        untaken[i] -= x;
        t += x;
        u -= x;
    }
    for ( int i = 1; i <= m; i++ ) {
        long long x = min( untaken[i], (l - s) / i );
        s += i * x;
        taken[i] += x;
        untaken[i] -= x;
        t += x;
        u -= x;
    }

    if ( s + m < l ) {
        for ( int i = -m; i < 0; i++ ) {
            long long x = min( taken[i], (l - s) / (-i) );
            s -= i * x;
            taken[i] -= x;
            untaken[i] += x;
            t -= x;
            u += x;
        }
    }

    for ( int s = MIN_S; s <= MAX_S; s++ )
        dpCrt[s] = -INF;
    dpCrt[0] = 0;

    for ( int i = -m; i <= m; i++ ) {
        int k, s;

        s = 0;
        k = min( (long long)m, untaken[i] );
        for ( int b = 0; s + (1 << b) <= k; s += (1 << b), b++ )
            add( (1 << b), i );
        add( k - s, i );

        s = 0;
        k = min( (long long)m, taken[i] );
        for ( int b = 0; s + (1 << b) <= k; s += (1 << b), b++ )
            substract( (1 << b), i );
        substract( k - s, i );
    }


    if ( l - s > MAX_S || dpCrt[l - s] == -INF )
        cout << "impossible\n";
    else
        cout << t + dpCrt[l - s] << "\n";

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 18324 KB Output is correct
2 Correct 306 ms 18332 KB Output is correct
3 Correct 155 ms 18284 KB Output is correct
4 Correct 1024 ms 18320 KB Output is correct
5 Execution timed out 5058 ms 18312 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 18324 KB Output is correct
2 Correct 306 ms 18332 KB Output is correct
3 Correct 155 ms 18284 KB Output is correct
4 Correct 1024 ms 18320 KB Output is correct
5 Execution timed out 5058 ms 18312 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3-1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1136 ms 18328 KB Output is correct
2 Correct 3516 ms 18332 KB Output is correct
3 Correct 2338 ms 18332 KB Output is correct
4 Correct 3689 ms 18332 KB Output is correct
5 Correct 3995 ms 18424 KB Output is correct
6 Correct 3484 ms 18328 KB Output is correct
7 Correct 2170 ms 18332 KB Output is correct
8 Correct 2165 ms 18328 KB Output is correct
9 Correct 2748 ms 18332 KB Output is correct
10 Correct 3102 ms 18328 KB Output is correct

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1136 ms 18328 KB Output is correct
2 Correct 3516 ms 18332 KB Output is correct
3 Correct 2338 ms 18332 KB Output is correct
4 Correct 3689 ms 18332 KB Output is correct
5 Correct 3995 ms 18424 KB Output is correct
6 Correct 3484 ms 18328 KB Output is correct
7 Correct 2170 ms 18332 KB Output is correct
8 Correct 2165 ms 18328 KB Output is correct
9 Correct 2748 ms 18332 KB Output is correct
10 Correct 3102 ms 18328 KB Output is correct
11 Correct 298 ms 18332 KB Output is correct
12 Correct 312 ms 18324 KB Output is correct
13 Correct 145 ms 18328 KB Output is correct
14 Correct 1047 ms 18308 KB Output is correct
15 Correct 3634 ms 18348 KB Output is correct
16 Correct 2393 ms 18336 KB Output is correct
17 Correct 3804 ms 18336 KB Output is correct
18 Correct 3980 ms 18332 KB Output is correct
19 Correct 3494 ms 18312 KB Output is correct
20 Correct 2205 ms 18328 KB Output is correct
21 Correct 2278 ms 18336 KB Output is correct
22 Correct 2834 ms 18328 KB Output is correct
23 Correct 3193 ms 18336 KB Output is correct
24 Execution timed out 5051 ms 18308 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1136 ms 18328 KB Output is correct
2 Correct 3516 ms 18332 KB Output is correct
3 Correct 2338 ms 18332 KB Output is correct
4 Correct 3689 ms 18332 KB Output is correct
5 Correct 3995 ms 18424 KB Output is correct
6 Correct 3484 ms 18328 KB Output is correct
7 Correct 2170 ms 18332 KB Output is correct
8 Correct 2165 ms 18328 KB Output is correct
9 Correct 2748 ms 18332 KB Output is correct
10 Correct 3102 ms 18328 KB Output is correct
11 Correct 1082 ms 18324 KB Output is correct
12 Correct 3513 ms 18336 KB Output is correct
13 Correct 2398 ms 18336 KB Output is correct
14 Correct 3784 ms 18340 KB Output is correct
15 Correct 4030 ms 18336 KB Output is correct
16 Correct 3574 ms 18328 KB Output is correct
17 Correct 2319 ms 18336 KB Output is correct
18 Correct 2138 ms 18332 KB Output is correct
19 Correct 2897 ms 18328 KB Output is correct
20 Correct 3093 ms 18332 KB Output is correct
21 Correct 3429 ms 18336 KB Output is correct
22 Correct 3349 ms 18340 KB Output is correct
23 Execution timed out 5030 ms 18312 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 18324 KB Output is correct
2 Correct 306 ms 18332 KB Output is correct
3 Correct 155 ms 18284 KB Output is correct
4 Correct 1024 ms 18320 KB Output is correct
5 Execution timed out 5058 ms 18312 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1136 ms 18328 KB Output is correct
2 Correct 3516 ms 18332 KB Output is correct
3 Correct 2338 ms 18332 KB Output is correct
4 Correct 3689 ms 18332 KB Output is correct
5 Correct 3995 ms 18424 KB Output is correct
6 Correct 3484 ms 18328 KB Output is correct
7 Correct 2170 ms 18332 KB Output is correct
8 Correct 2165 ms 18328 KB Output is correct
9 Correct 2748 ms 18332 KB Output is correct
10 Correct 3102 ms 18328 KB Output is correct
11 Correct 1082 ms 18324 KB Output is correct
12 Correct 3513 ms 18336 KB Output is correct
13 Correct 2398 ms 18336 KB Output is correct
14 Correct 3784 ms 18340 KB Output is correct
15 Correct 4030 ms 18336 KB Output is correct
16 Correct 3574 ms 18328 KB Output is correct
17 Correct 2319 ms 18336 KB Output is correct
18 Correct 2138 ms 18332 KB Output is correct
19 Correct 2897 ms 18328 KB Output is correct
20 Correct 3093 ms 18332 KB Output is correct
21 Correct 3429 ms 18336 KB Output is correct
22 Correct 3349 ms 18340 KB Output is correct
23 Execution timed out 5030 ms 18312 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 18324 KB Output is correct
2 Correct 306 ms 18332 KB Output is correct
3 Correct 155 ms 18284 KB Output is correct
4 Correct 1024 ms 18320 KB Output is correct
5 Execution timed out 5058 ms 18312 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1136 ms 18328 KB Output is correct
2 Correct 3516 ms 18332 KB Output is correct
3 Correct 2338 ms 18332 KB Output is correct
4 Correct 3689 ms 18332 KB Output is correct
5 Correct 3995 ms 18424 KB Output is correct
6 Correct 3484 ms 18328 KB Output is correct
7 Correct 2170 ms 18332 KB Output is correct
8 Correct 2165 ms 18328 KB Output is correct
9 Correct 2748 ms 18332 KB Output is correct
10 Correct 3102 ms 18328 KB Output is correct
11 Correct 1082 ms 18324 KB Output is correct
12 Correct 3513 ms 18336 KB Output is correct
13 Correct 2398 ms 18336 KB Output is correct
14 Correct 3784 ms 18340 KB Output is correct
15 Correct 4030 ms 18336 KB Output is correct
16 Correct 3574 ms 18328 KB Output is correct
17 Correct 2319 ms 18336 KB Output is correct
18 Correct 2138 ms 18332 KB Output is correct
19 Correct 2897 ms 18328 KB Output is correct
20 Correct 3093 ms 18332 KB Output is correct
21 Correct 3429 ms 18336 KB Output is correct
22 Correct 3349 ms 18340 KB Output is correct
23 Execution timed out 5030 ms 18312 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 18324 KB Output is correct
2 Correct 306 ms 18332 KB Output is correct
3 Correct 155 ms 18284 KB Output is correct
4 Correct 1024 ms 18320 KB Output is correct
5 Execution timed out 5058 ms 18312 KB Time limit exceeded
6 Halted 0 ms 0 KB -