제출 #127524

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
127524		OptxPrime	Kitchen (BOI19_kitchen)	C++11	41 / 100	130 ms	111228 KiB

kitchen

#include <iostream>
#include <cmath>
#include<vector>
#include <algorithm>
#include <utility>
#include<stack>
#include<queue>
#include<map>
#include <fstream>

using namespace std;

#define pb push_back
#define mp make_pair
#define ll long long
#define maxn 310

int inf=1000000000;
int a[310],b[310];
int dp[310][maxn*maxn];

    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        int n,m,k;
        int mealsum=0,sum=0;
        bool is=true;
        cin>>n>>m>>k;
        for( int i=1;i<=n;i++ ) {
            cin>>a[i];
            if( a[i] < k ){
              is=false;
              //  return 0;
            }
            mealsum+=a[i];
        }
        for( int i=1;i<=m;i++ ){
            cin>>b[i];
            sum+=b[i];
        }
        if(!is){
            cout << "Impossible" <<endl;
            return 0;
        }
        sum = 305*305;
      for( int i=0;i<=m;i++ ){
        for( int j=0;j<=sum;j++ ) dp[i][j]=-inf;
      }
      dp[0][0]=0;
      for( int i=1;i<=m;i++ ){
        for( int j=1;j<=sum;j++ ){
                if( j - b[i] >=0 )
            dp[i][j] = max( dp[i-1][j], dp[i-1][ j - b[i] ] + min( n,b[i] ) );
        else dp[i][j]=dp[i-1][j];
        }
      }

      for( int i = mealsum;i<= sum;i++ ){
        if( dp[m][i] >= n*k ){
            cout << i - mealsum << endl;
            return 0;
        }
      }
      cout << "Impossible" <<endl;
      return 0;
    }

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