Submission #624918

#TimeUsernameProblemLanguageResultExecution timeMemory
624918QwertyPiBoat (APIO16_boat)C++14
36 / 100
2081 ms8652 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 520; const int M = 1e9 + 7; int a[N], b[N]; int d[N * 2]; int dp[2][N * 2][N]; int n, m; int pm(int a, int b){ if(b == 0) return 1; return pm(a * a % M, b / 2) * (b % 2 ? a : 1) % M; } int mi(int a){ return pm(a, M - 2); } int fact[N]; int32_t main(){ cin >> n; for(int i = 0; i < n; i++){ cin >> a[i] >> b[i]; } vector<int> sp; sp.push_back(0); sp.push_back(1); for(int i = 0; i < n; i++){ sp.push_back(a[i]); sp.push_back(b[i] + 1); } sort(sp.begin(), sp.end()); sp.resize(unique(sp.begin(), sp.end()) - sp.begin()); m = sp.size(); { map<int, int> M; for(int i = 0; i < m; i++) M[sp[i]] = i; for(int i = 0; i < n; i++) a[i] = M[a[i]], b[i] = M[b[i] + 1]; } for(int i = 0; i < m - 1; i++){ d[i] = sp[i + 1] - sp[i]; } int ans = 0; /* for(int j = 0; j < m; j++){ for(int k = 0; k <= n; k++){ cout << dp[0][j][k] << ' '; } cout << endl; } cout << endl; */ for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ for(int k = 1; k <= n; k++){ dp[(i + 1) % 2][j][k] = dp[i % 2][j][k]; } } int s[m + 1] = {0}; for(int j = 0; j < m; j++){ for(int k = 0; k <= n; k++){ s[j + 1] += dp[i % 2][j][k]; } s[j] %= M; s[j + 1] += s[j]; } /* for(int j = 0; j < m; j++){ for(int k = 0; k <= n; k++){ cout << dp[(i + 1) % 2][j][k] << ' '; } cout << endl; } cout << endl; */ for(int j = a[i]; j < b[i]; j++){ dp[(i + 1) % 2][j][1] += (s[j] + 1) * d[j] % M; for(int k = 1; k < n; k++){ dp[(i + 1) % 2][j][k + 1] += dp[i % 2][j][k] * (d[j] - k) % M * mi(k + 1) % M; } } for(int j = 0; j < m; j++){ for(int k = 1; k <= n; k++){ dp[(i + 1) % 2][j][k] %= M; } } if(i == 0){ dp[0][0][0] = 0; } /* for(int j = 0; j < m; j++){ for(int k = 0; k <= n; k++){ cout << dp[(i + 1) % 2][j][k] << ' '; } cout << endl; } cout << endl; */ } for(int j = 0; j < m; j++){ for(int k = 1; k <= n; k++){ ans += dp[n % 2][j][k]; } } ans %= M; cout << ans << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...