제출 #925793

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
925793		vjudge1	Kitchen (BOI19_kitchen)	C++17	0 / 100	0 ms	348 KiB

kitchen

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define emb emplace_back
#define emc emplace
#define pii pair<int,int>
#define pll pair<ll,ll>
#define F first
#define S second
template <class type_key, class type_val>
using um = unordered_map<type_key, type_val>;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

signed main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
      
      int n, m, k;
      cin >> n >> m >> k;

      int a[n+1];
      int tota = 0, totb = 0;
      for( int i = 1; i <= n; i++ ) {
            cin >> a[i];
            tota += a[i];
      }

      int b[m+1];
      for( int j = 1; j <= m; j++ ) {
            cin >> b[j];
            totb += b[j];
      }

      if( k > m || tota > totb ) return cout << "Impossible", 0;

      if( k == 1 ) {
            sort(b+1,b+m+1);

            int chef = 1;
            for( int i = 1; i <= n; i++ ) {
                  for( ; chef <= m; chef++ ) {
                        if( a[i] > b[chef] ) {
                              a[i] -= b[chef];
                              b[chef] = 0;
                        } else {
                              b[chef] -= a[i];
                              a[i] = 0;
                              break;
                        }
                  }
            }

            cout << b[chef];
      } else {
            sort(b+1,b+m+1);

            int chef = 1;
            int _last = 1;
            for( int i = 1; i <= n; i++ ) {
                  int cnt = 0;
                  if( a[i] < k ) {
                        return cout << "Impossible", 0;
                  }
                  while( b[chef] == 0 ) chef--;
                  for( int j = chef; j <= m; j++ ) {
                        if( k == cnt && a[i] <= 0 ) break;
                        if( b[j] >= a[i]-(k-cnt-1) ) {
                              int temp = a[i];
                              a[i] -= a[i]-(k-cnt-1);
                              b[j] -= temp-(k-cnt-1);
                              cnt++;
                              _last = max(j, _last);
                        } else {
                              if( b[j] == 0 ) continue;
                              else {
                                    a[i] -= b[j];
                                    b[j] = 0;
                                    cnt++;
                                    _last = max(j, _last);
                              }
                        }
                  }
                  if( !(k == cnt && a[i] <= 0) ) {
                        return cout << "Impossible", 0;
                  }
            }

            ll extra = 0;
            for( int i = chef; i <= _last; i++ ) {
                  extra += b[i];
            }
            cout << extra;
      }

return 0;
}

// @@@#$

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 20
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28