Submission #494896

#TimeUsernameProblemLanguageResultExecution timeMemory
494896XIIBoat (APIO16_boat)C++17
100 / 100
528 ms2456 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define fi first #define se second #define mp make_pair #define eb emplace_back #define ALL(x) (x).begin(), (x).end() #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORU(i, a, b) for(int i = (a); i <= (b); ++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define IOS cin.tie(0)->sync_with_stdio(false); #define PROB "DUT03TEAMS" void Fi(){ if(fopen(PROB".inp", "r")){ freopen(PROB".inp", "r", stdin); freopen(PROB".out", "w", stdout); } } const int N = 500 + 1; const int MOD = 1e9 + 7; int a[N], b[N], n, m; int dp[N][N << 1]; int X[N << 1]; int inv[N]; int add(const int &a, const int &b){ return (a + b >= MOD ? a + b - MOD : a + b); } int mul(const int &a, const int &b){ return (1LL * a * b) % MOD; } void compress(){ sort(X + 1, X + m + 1); m = unique(X + 1, X + m + 1) - X; FORU(i, 1, n){ a[i] = lower_bound(X + 1, X + m, a[i]) - X; b[i] = lower_bound(X + 1, X + m, b[i]) - X; // cout << a[i] << " " << b[i] << "\n"; } m -= 2; // cout << m << "\n"; } int main(){ IOS; Fi(); cin >> n; FORU(i, 1, n){ cin >> a[i] >> b[i]; X[++m] = a[i]; X[++m] = ++b[i]; } compress(); inv[1] = 1; FORU(i, 2, n){ inv[i] = mul(MOD - MOD / i, inv[MOD % i]); } int ans = 0; FORU(j, 0, m) dp[0][j] = 1; FORU(i, 1, n){ FOR(j, a[i], b[i]){ int len = X[j + 1] - X[j]; int C = len, cnt = 1; FORD(k, i - 1, 0){ dp[i][j] = add(dp[i][j], mul(dp[k][j - 1], C)); if(a[k] <= j && j < b[k]){ ++cnt; C = mul(mul(C, len + cnt - 1), inv[cnt]); } } } FORU(j, 2, m) dp[i][j] = add(dp[i][j], dp[i][j - 1]); ans = add(ans, dp[i][m]); } cout << ans; return 0; }

Compilation message (stderr)

boat.cpp: In function 'void Fi()':
boat.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...