oj.uz

Submission #567118

# Submission time Handle Problem Language Result Execution time Memory
567118 2022-05-23T08:12:50 Z almothana05 Kitchen (BOI19_kitchen) C++14
31 / 100
 15 ms 1080 KB 
#include<bits/stdc++.h>
#define mod 1000000007
#define inf 100000000000000000
using namespace std;
vector<int>num, chef , pow2;
pair<int ,int>mask[40000];
int sub[400][300 * 400];
void im(){
   cout << "Impossible\n";
}
string bi(int x){
   string cmp;
   while(x){
      if(x % 2 == 0){
         cmp += '0';
      }
      else{
         cmp += '1';
      }
      x /= 2;
   }
   return cmp;
}
int main(){
   // ios_base::sync_with_stdio(false);
   // cin.tie(NULL);
   for(int i = 1; i < 1000000 ; i *= 2){
      pow2.push_back(i);
   }
   int menge,  numm , nummer , koch , mini , re = 0 , rechner = 0;
   cin >> menge >> koch >> mini;
   if(koch < mini){
      im();
      return 0;
   }
   for(int i = 0 ; i < menge ; i++){
      cin >> numm;
      re += numm;
      num.push_back(numm);
      if(numm < mini){
         im();
         return 0;
      }
   }
   for(int i = 0 ; i < koch ; i++){
      cin >> numm;
      rechner += numm;
      chef.push_back(numm);
   }
   ///////////////////////////////////////////////////////////////////////////////////////////
   // if(mini == 1){
   //    sub[0][0] = 1;
   //    for(int i = 0 ; i < koch ; i++){
   //       for(int j = 0 ; j <= 300 * 300 ; j++){
   //          if(sub[i][j] == 1){
   //             sub[i + 1][j] = 1;
   //             sub[i + 1][j + num[i]] = 1;
   //          }
   //       }
   //    }
   //    int erg = -1;
   //    for(int i = rechner - re ; i >= 0 ; i--){
   //       if(sub[koch][i] == 1){
   //          erg = rechner - re - i;
   //          break;   
   //       }
   //    }
   //    if(erg == -1){
   //       im();
   //       return 0;
   //    }
   //    else{
   //       cout << erg << "\n";
   //    }
   //    return 0;
   // }
   mask[0] = {menge * mini , re};
   string s;
   for(int i = 1 ; i < pow2[koch] ; i++){
      s = bi(i);
      for(int j = 0 ; j < s.size() ; j++){
         if(s[j] == '1'){
            mask[i] = mask[i - pow2[j]];
            mask[i].first -= min(menge , chef[j]);
            mask[i].second -= chef[j];
         }
      }
   }
   int erg = mod;
   for(int i = 0 ; i < pow2[koch] ; i++){
      if(mask[i].first <= 0 && mask[i].second <= 0){
         erg = min(erg , -mask[i].second);
      }
   }
   if(erg == mod){
      im();
      return 0;
   }
   assert(erg>= 0);
   cout << erg << "\n";
}

Compilation message

kitchen.cpp: In function 'int main()':
kitchen.cpp:81:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |       for(int j = 0 ; j < s.size() ; j++){
      |                       ~~^~~~~~~~~~
kitchen.cpp:30:23: warning: unused variable 'nummer' [-Wunused-variable]
   30 |    int menge,  numm , nummer , koch , mini , re = 0 , rechner = 0;
      |                       ^~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 6 ms 468 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 7 ms 492 KB Output is correct
13 Correct 7 ms 568 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 1080 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 15 ms 1072 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 6 ms 468 KB Output is correct
11 Correct 5 ms 468 KB Output is correct
12 Correct 7 ms 492 KB Output is correct
13 Correct 7 ms 568 KB Output is correct
14 Runtime error 13 ms 1080 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -