# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
127520 | 2019-07-09T13:38:07 Z | OptxPrime | Kitchen (BOI19_kitchen) | C++11 | 176 ms | 107964 KB |
#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 int inf=1000000000; int a[310],b[310]; int dp[310][91000]; 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*505; 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; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1656 KB | Output is correct |
2 | Incorrect | 3 ms | 1656 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1656 KB | Output is correct |
2 | Incorrect | 3 ms | 1656 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 138 ms | 93944 KB | Output is correct |
2 | Correct | 120 ms | 81496 KB | Output is correct |
3 | Correct | 163 ms | 107964 KB | Output is correct |
4 | Correct | 176 ms | 107788 KB | Output is correct |
5 | Incorrect | 175 ms | 104228 KB | Output isn't correct |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 15224 KB | Output is correct |
2 | Correct | 23 ms | 15224 KB | Output is correct |
3 | Correct | 24 ms | 15224 KB | Output is correct |
4 | Correct | 24 ms | 15224 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1656 KB | Output is correct |
2 | Incorrect | 3 ms | 1656 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |