oj.uz

Submission #115337

# Submission time Handle Problem Language Result Execution time Memory
115337 2019-06-06T17:25:23 Z model_code Hotel (CEOI11_hot) C++17
10 / 100
 4000 ms 10332 KB 
/* Slow solution for task HOT
 * Author: Miroslaw Michalski
 * Time complexity : O(2^(n+m))
 * 01MAY11
 */
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>

using namespace std;
int main() {
  int n, m, o, ci, pi;
  long long res = 0, w;
  vector<int> think;
  vector<pair<int, int> > q;
  vector<pair<int, int> > v;
  scanf("%d%d%d", &n, &m, &o);
  for(int i = 0; i < n; i++) {
    scanf("%d%d", &ci, &pi);
    v.push_back(make_pair(ci, pi));
  }
  for(int i = 0; i < m; i++) {
    scanf("%d%d", &ci, &pi);
    q.push_back(make_pair(ci, pi));
  }
  if (n > 50 || m > 50) { // so sinol would accept it as slow-correct
   while(true) {}
  } 

  for(int rooms = 0; rooms < (1<<n); rooms++) {
    for(int offers = 0; offers < (1<<m); offers++) 
      if (__builtin_popcount(rooms) <= o && 
          __builtin_popcount(rooms) == __builtin_popcount(offers)) {
        vector<int> g1, g2;
        w = 0;
        for(int i = 0; i < n; i++) if (rooms & (1<<i)) {
          w -= v[i].first;
          g1.push_back(v[i].second);
        }
        for(int i = 0; i < m; i++) if (offers & (1<<i)) {
          w += q[i].first;
          g2.push_back(q[i].second);
        }
        sort(g1.begin(), g1.end());
        sort(g2.begin(), g2.end());
        bool no = false;
        for(size_t i = 0; i < g2.size(); i++) {
          if (g1[i] < g2[i]) {
            no = true;
          }
        }
        if (!no) {
          res = max(res, w);
        }
      }
  }
  printf("%lld\n", res);
  return 0;
}

Compilation message

hot.cpp: In function 'int main()':
hot.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &m, &o);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
hot.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &ci, &pi);
     ~~~~~^~~~~~~~~~~~~~~~~~
hot.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &ci, &pi);
     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 256 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4091 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4089 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4005 ms 256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4072 ms 512 KB Time limit exceeded

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4082 ms 1400 KB Time limit exceeded

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4070 ms 2408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4043 ms 4936 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4003 ms 9568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4022 ms 10332 KB Time limit exceeded
2 Halted 0 ms 0 KB -