Submission #1344701

#TimeUsernameProblemLanguageResultExecution timeMemory
1344701ramzialoulouBoat (APIO16_boat)C++20
31 / 100
497 ms589824 KiB
#include <bits/stdc++.h>
 
using namespace std;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int> a(n + 1), b(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
  }
  vector<vector<int>> dp(n + 1);
  for (int i = 0; i <= n; i++) {
    dp[i].resize(b[i] - a[i] + 1);
  }
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < i; j++) {
      for (int x = a[j]; x <= b[j]; x++) {
        if (x + 1 <= b[i]) {
          int k = max(0, x + 1 - a[i]);
          dp[i][k] += dp[j][x - a[j]];
          dp[i][k] %= md;
        }
      }
    }
    for (int x = a[i] + 1; x <= b[i]; x++) {
      dp[i][x - a[i]] += dp[i][x - 1 - a[i]];
      dp[i][x - a[i]] %= md;
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int x = a[i]; x <= b[i]; x++) {
      ans += dp[i][x - a[i]];
      ans %= md;
    }
  }
  cout << ans << '\n';
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...