Submission #1051485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051485		NeroZein	Fire (BOI24_fire)	C++17	14 / 100	312 ms	432 KiB

Main

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m;
  cin >> n >> m;
  vector<int> s(n), e(n); 
  for (int i = 0; i < n; ++i) {
    cin >> s[i] >> e[i];
  }
  int ans = n + 1; 
  for (int mask = 1; mask < (1 << n); ++mask) {
    vector<pair<int, int>> ranges;
    for (int i = 0; i < n; ++i) {
      if (mask >> i & 1) {
        if (s[i] <= e[i]) {
          ranges.push_back({s[i], e[i]});
        } else {
          ranges.push_back({s[i], m - 1});
          ranges.push_back({0, e[i]});
        }
      }
    }
    bool ok = true; 
    sort(ranges.begin(), ranges.end()); 
    int mx = 0;
    for (int i = 0; i < (int) ranges.size(); ++i) {
      auto [l, r] = ranges[i];
      if (mx < l) {
        ok = false;
        break; 
      }
      mx = max(mx, r); 
    }
    ok &= mx == m - 1;
    if (ok) {
      ans = min(ans, __builtin_popcount(mask)); 
    }
  }
  cout << (ans > n ? -1 : ans) << '\n';
  return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 17
• Subtask 3: 0 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26