oj.uz

Submission #943667

# Submission time Handle Problem Language Result Execution time Memory
943667 2024-03-11T17:50:42 Z LucaIlie Uplifting Excursion (BOI22_vault) C++17
5 / 100
 5000 ms 2132 KB 
#include <bits/stdc++.h>

using namespace std;

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

int main() {
    int m;
    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 <= -1; i++ ) {
        swap( dpCrt, dpPrv );

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

        for ( int x = 0; x <= m && x <= untaken[i]; x++ ) {
            for ( int s = MIN_S; s - i * x <= MAX_S; s++ )
                dpCrt[s] = max( dpCrt[s], dpPrv[s - i * x] + x );
        }
        for ( int x = 0; x <= m && x <= taken[i]; x++ ) {
            for ( int s = MIN_S - i * x; s <= MAX_S; s++ )
                dpCrt[s] = max( dpCrt[s], dpPrv[s + i * x] - x );
        }
        /*for ( int s = MIN_S; s <= MAX_S; s++ )
            cout << dpCrt[s] << " ";
        cout << "\n";*/
    }
    for ( int i = 0; i <= m; i++ ) {
        swap( dpCrt, dpPrv );

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

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

        /*for ( int s = MIN_S; s <= MAX_S; s++ )
            cout << dpCrt[s] << " ";
        cout << "\n";*/
    }

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

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1884 KB Output is correct
2 Correct 16 ms 2024 KB Output is correct
3 Correct 8 ms 1884 KB Output is correct
4 Correct 64 ms 1880 KB Output is correct
5 Correct 1514 ms 2012 KB Output is correct
6 Correct 1620 ms 2016 KB Output is correct
7 Correct 726 ms 2008 KB Output is correct
8 Correct 1545 ms 2012 KB Output is correct
9 Correct 2825 ms 2008 KB Output is correct
10 Correct 205 ms 2012 KB Output is correct
11 Correct 178 ms 2012 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1884 KB Output is correct
2 Correct 16 ms 2024 KB Output is correct
3 Correct 8 ms 1884 KB Output is correct
4 Correct 64 ms 1880 KB Output is correct
5 Correct 1514 ms 2012 KB Output is correct
6 Correct 1620 ms 2016 KB Output is correct
7 Correct 726 ms 2008 KB Output is correct
8 Correct 1545 ms 2012 KB Output is correct
9 Correct 2825 ms 2008 KB Output is correct
10 Correct 205 ms 2012 KB Output is correct
11 Correct 178 ms 2012 KB Output is correct
12 Correct 14 ms 1884 KB Output is correct
13 Correct 16 ms 2024 KB Output is correct
14 Correct 9 ms 1884 KB Output is correct
15 Correct 67 ms 1884 KB Output is correct
16 Correct 1544 ms 2012 KB Output is correct
17 Correct 1626 ms 2012 KB Output is correct
18 Correct 709 ms 2012 KB Output is correct
19 Correct 1558 ms 2008 KB Output is correct
20 Correct 2733 ms 2008 KB Output is correct
21 Correct 198 ms 2020 KB Output is correct
22 Correct 178 ms 2016 KB Output is correct
23 Execution timed out 5021 ms 1884 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1996 KB Output is correct
2 Correct 418 ms 2004 KB Output is correct
3 Correct 180 ms 2012 KB Output is correct
4 Correct 501 ms 2004 KB Output is correct
5 Correct 586 ms 2024 KB Output is correct
6 Correct 386 ms 2132 KB Output is correct
7 Correct 146 ms 2008 KB Output is correct
8 Correct 130 ms 2004 KB Output is correct
9 Incorrect 249 ms 1880 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1996 KB Output is correct
2 Correct 418 ms 2004 KB Output is correct
3 Correct 180 ms 2012 KB Output is correct
4 Correct 501 ms 2004 KB Output is correct
5 Correct 586 ms 2024 KB Output is correct
6 Correct 386 ms 2132 KB Output is correct
7 Correct 146 ms 2008 KB Output is correct
8 Correct 130 ms 2004 KB Output is correct
9 Incorrect 249 ms 1880 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1996 KB Output is correct
2 Correct 418 ms 2004 KB Output is correct
3 Correct 180 ms 2012 KB Output is correct
4 Correct 501 ms 2004 KB Output is correct
5 Correct 586 ms 2024 KB Output is correct
6 Correct 386 ms 2132 KB Output is correct
7 Correct 146 ms 2008 KB Output is correct
8 Correct 130 ms 2004 KB Output is correct
9 Incorrect 249 ms 1880 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1884 KB Output is correct
2 Correct 16 ms 2024 KB Output is correct
3 Correct 8 ms 1884 KB Output is correct
4 Correct 64 ms 1880 KB Output is correct
5 Correct 1514 ms 2012 KB Output is correct
6 Correct 1620 ms 2016 KB Output is correct
7 Correct 726 ms 2008 KB Output is correct
8 Correct 1545 ms 2012 KB Output is correct
9 Correct 2825 ms 2008 KB Output is correct
10 Correct 205 ms 2012 KB Output is correct
11 Correct 178 ms 2012 KB Output is correct
12 Correct 64 ms 1996 KB Output is correct
13 Correct 418 ms 2004 KB Output is correct
14 Correct 180 ms 2012 KB Output is correct
15 Correct 501 ms 2004 KB Output is correct
16 Correct 586 ms 2024 KB Output is correct
17 Correct 386 ms 2132 KB Output is correct
18 Correct 146 ms 2008 KB Output is correct
19 Correct 130 ms 2004 KB Output is correct
20 Incorrect 249 ms 1880 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1996 KB Output is correct
2 Correct 418 ms 2004 KB Output is correct
3 Correct 180 ms 2012 KB Output is correct
4 Correct 501 ms 2004 KB Output is correct
5 Correct 586 ms 2024 KB Output is correct
6 Correct 386 ms 2132 KB Output is correct
7 Correct 146 ms 2008 KB Output is correct
8 Correct 130 ms 2004 KB Output is correct
9 Incorrect 249 ms 1880 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1884 KB Output is correct
2 Correct 16 ms 2024 KB Output is correct
3 Correct 8 ms 1884 KB Output is correct
4 Correct 64 ms 1880 KB Output is correct
5 Correct 1514 ms 2012 KB Output is correct
6 Correct 1620 ms 2016 KB Output is correct
7 Correct 726 ms 2008 KB Output is correct
8 Correct 1545 ms 2012 KB Output is correct
9 Correct 2825 ms 2008 KB Output is correct
10 Correct 205 ms 2012 KB Output is correct
11 Correct 178 ms 2012 KB Output is correct
12 Correct 14 ms 1884 KB Output is correct
13 Correct 16 ms 2024 KB Output is correct
14 Correct 9 ms 1884 KB Output is correct
15 Correct 67 ms 1884 KB Output is correct
16 Correct 1544 ms 2012 KB Output is correct
17 Correct 1626 ms 2012 KB Output is correct
18 Correct 709 ms 2012 KB Output is correct
19 Correct 1558 ms 2008 KB Output is correct
20 Correct 2733 ms 2008 KB Output is correct
21 Correct 198 ms 2020 KB Output is correct
22 Correct 178 ms 2016 KB Output is correct
23 Execution timed out 5021 ms 1884 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 1996 KB Output is correct
2 Correct 418 ms 2004 KB Output is correct
3 Correct 180 ms 2012 KB Output is correct
4 Correct 501 ms 2004 KB Output is correct
5 Correct 586 ms 2024 KB Output is correct
6 Correct 386 ms 2132 KB Output is correct
7 Correct 146 ms 2008 KB Output is correct
8 Correct 130 ms 2004 KB Output is correct
9 Incorrect 249 ms 1880 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1884 KB Output is correct
2 Correct 16 ms 2024 KB Output is correct
3 Correct 8 ms 1884 KB Output is correct
4 Correct 64 ms 1880 KB Output is correct
5 Correct 1514 ms 2012 KB Output is correct
6 Correct 1620 ms 2016 KB Output is correct
7 Correct 726 ms 2008 KB Output is correct
8 Correct 1545 ms 2012 KB Output is correct
9 Correct 2825 ms 2008 KB Output is correct
10 Correct 205 ms 2012 KB Output is correct
11 Correct 178 ms 2012 KB Output is correct
12 Correct 14 ms 1884 KB Output is correct
13 Correct 16 ms 2024 KB Output is correct
14 Correct 9 ms 1884 KB Output is correct
15 Correct 67 ms 1884 KB Output is correct
16 Correct 1544 ms 2012 KB Output is correct
17 Correct 1626 ms 2012 KB Output is correct
18 Correct 709 ms 2012 KB Output is correct
19 Correct 1558 ms 2008 KB Output is correct
20 Correct 2733 ms 2008 KB Output is correct
21 Correct 198 ms 2020 KB Output is correct
22 Correct 178 ms 2016 KB Output is correct
23 Execution timed out 5021 ms 1884 KB Time limit exceeded
24 Halted 0 ms 0 KB -