oj.uz

Submission #925703

# Submission time Handle Problem Language Result Execution time Memory
925703 2024-02-12T07:39:38 Z vjudge1 Kitchen (BOI19_kitchen) C++17
51 / 100
 100 ms 9912 KB 
// By ObeliX
#include <bits/stdc++.h>
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <unordered_map>
#include <cstddef>
#include <cassert>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

const long long N = 1e6 + 5;
const long long mod = 1e7 + 7;
const long long INF = 1e18;

long long n , m , k;
long long a[N] , b[N] , a1[N];
long long dp[3][N];

int main(){
    //freopen( "cinema.in" , "r" , stdin );
    //freopen( "cinema.out" , "w" , stdout );
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> k;
    for ( int i = 1 ; i <= n ; i++ ) {
        cin >> a[i];
        a1[i] = a[i];
    }
    for ( int i = 1 ; i <= m ; i++ ) {
        cin >> b[i];
    }
    if ( k > m ) {
        cout << "Impossible";
        return 0;
    }
    if ( k == 1 ) {
        sort( b + 1 , b + 1 + m );
        long long sum = 0;
        for ( int i = 1 ; i <= n ; i++ ) {
            sum += a[i];
        }
        dp[1][0] = 1;
        for ( int i = 1 ; i <= m ; i++ ) {
            for ( int j = b[i] ; j <= 100000 ; j++ ) {
                dp[2][j] = max( dp[2][j] , dp[1][j-b[i]] );
            }
            for ( int j = 0 ; j <= 100000 ; j++ ) {
                dp[1][j] = max( dp[2][j] , dp[1][j] );
                dp[2][j] = 0;
            }
        }
        long long ans = -1;
        for ( int i = sum ; i <= 100000 ; i++ ) {
            if ( dp[1][i] == 1 ) {
                ans = i;
                break;
            }
        }
        if ( ans == -1 ) {
            cout << "Impossible";
        }
        else {
            cout << ans - sum;
        }
    }
    else {
        sort( b + 1 , b + 1 + m );
        long long sum1 = 0 , sum3 = 0;
        for ( int i = 1 ; i <= n ; i++ ) {
            sum1 += a[i];
            if ( a[i] < k ) {
                sum1 = -1;
                break;
            }
        }
        for ( int i = 1 ; i <= m ; i++ ) {
            sum3 += b[i];
        }
        if ( sum1 == -1 || sum3 < sum1 ) {
            cout << "Impossible";
            return 0;
        }  
        long long ans = INF;
        for ( int mask = 0 ; mask <= ( ( 1 << m ) - 1 ) ; mask++ ) {
            if ( __builtin_popcount( mask ) < k ) {
                continue;
            }
            vector <long long> v;
            long long sum2 = 0;
            for ( int i = 0 ; i < m ; i++ ) {
                if ( ((mask >> i) & 1) ) {
                    v.push_back( b[i+1] );
                    sum2 += b[i+1];
                }
            }
            if ( sum1 > sum2 ) {
                continue;
            }
            for ( int i = 1 ; i <= n ; i++ ) {
                a[i] = a1[i];
            }
            long long can = 0;
            for ( int j = 1 ; j <= n ; j++ ) {
                if ( a[j] < k ) {
                    can = 1;
                    break;
                }
                else {
                    a[j] -= k;
                    long long cnt = 0;
                    for ( int i = v.size() - 1 ; i >= 0 ; i-- ) {
                        if ( v[i] != 0 ) {
                            v[i]--;
                            cnt++;
                        }
                        else {
                            cnt = -1;
                            break;
                        }
                        if ( cnt == k ) {
                            break;
                        }
                    }
                    if ( cnt != k ) {
                        can = 1;
                        break;
                    }
                    sort( v.begin() , v.end() );
                }
            } 
            if ( can == 1 ) {
                continue;
            }
            long long sum = 0;
            for ( auto it : v ) {
                sum += it;
            }
            for ( int i = 1 ; i <= n ; i++ ) {
                sum -= a[i];
            }
            if ( sum < 0 ) {
                continue;
            }
            ans = min( sum , ans );
        }
        if ( ans == INF ) {
            cout << "Impossible";
        }
        else {
            cout << ans;
        }
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9672 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 3 ms 9564 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 ms 9564 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9672 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 3 ms 9564 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 ms 9564 KB Output is correct
9 Correct 4 ms 6744 KB Output is correct
10 Correct 9 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 6 ms 6492 KB Output is correct
13 Correct 12 ms 6608 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 9564 KB Output is correct
2 Correct 66 ms 9560 KB Output is correct
3 Correct 100 ms 9912 KB Output is correct
4 Correct 91 ms 9668 KB Output is correct
5 Correct 84 ms 9816 KB Output is correct
6 Correct 61 ms 9560 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 6492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9564 KB Output is correct
2 Correct 2 ms 9564 KB Output is correct
3 Correct 2 ms 9672 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 3 ms 9564 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 2 ms 9564 KB Output is correct
9 Correct 4 ms 6744 KB Output is correct
10 Correct 9 ms 6492 KB Output is correct
11 Correct 1 ms 6488 KB Output is correct
12 Correct 6 ms 6492 KB Output is correct
13 Correct 12 ms 6608 KB Output is correct
14 Correct 77 ms 9564 KB Output is correct
15 Correct 66 ms 9560 KB Output is correct
16 Correct 100 ms 9912 KB Output is correct
17 Correct 91 ms 9668 KB Output is correct
18 Correct 84 ms 9816 KB Output is correct
19 Correct 61 ms 9560 KB Output is correct
20 Incorrect 1 ms 6492 KB Output isn't correct
21 Halted 0 ms 0 KB -