Submission #875593

#	Time	Username	Problem	Language	Result	Execution time	Memory
875593		NeroZein	Boat (APIO16_boat)	C++17	31 / 100	1036 ms	524288 KiB

boat

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

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

const int md = (int) 1e9 + 7; 

void add(int& a, int b) {
  a += b;
  if (a >= md) a -= md; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n), b(n), c; 
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> b[i]; 
    for (int j = a[i]; j <= b[i]; ++j) {
      c.push_back(j); 
    }
  }
  sort(c.begin(), c.end());
  c.resize(unique(c.begin(), c.end()) - c.begin()); 
  vector<int> dp(n); 
  for (int i : c) {
    vector<int> pd(n); 
    for (int j = 0; j < n; ++j) {
      pd[j] = dp[j];
      dp[j] = 0; 
    }
    int s = 1; 
    for (int j = 0; j < n; ++j) {
      dp[j] = pd[j];
      if (a[j] <= i && b[j] >= i) {
        add(dp[j], s);         
      }
      add(s, pd[j]); 
    }
  }
  int ans = 0; 
  for (int i = 0; i < n; ++i) {
    add(ans, dp[i]); 
  }
  cout << ans << '\n'; 
  return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42