Submission #1085996

#TimeUsernameProblemLanguageResultExecution timeMemory
1085996Spy007Boat (APIO16_boat)C++17
100 / 100
265 ms10372 KiB
#define Name Spy007 #include <bits/stdc++.h> #define task "DL" #define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;++i) #define FOD(i,a,b) for (int i=(a),_b=(b);i>=_b;--i) #define fi first #define se second #define pb push_back #define mp make_pair #define All(x) x.begin(),x.end() #define sz(x) (int)x.size() #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define ll long long #define endl '\n' #define PI 3.14159265 using namespace std; typedef pair <int,int> ii; typedef pair <int,ii> iii; typedef pair <int,ll> ill; typedef pair <ll,ll> lll; typedef vector <int> vi; typedef vector <ii> vii; typedef vector <vi> vvi; const int nmax = 500; const ll mod = 1e9 + 7; int n, m; ll inv[nmax + 5], g[2 * nmax + 5][nmax + 5], c[nmax + 5][nmax + 5], dp[nmax + 5][2 * nmax + 5]; ii a[nmax + 5]; vi val; ll Pow(ll a, ll b) { if (b == 1) return a % mod; ll tmp = Pow(a, b / 2); tmp = (tmp * tmp) % mod; if (b & 1) return (tmp * a) % mod; else return tmp; } vi Treat(vi val) { sort(All(val)); vi ans; ans.pb(val[0]); FOR(i, 1, sz(val) - 1) if (val[i] != val[i - 1]) ans.pb(val[i]); return ans; } void Prep(void) { val = Treat(val); FOR(i, 1, n) inv[i] = Pow(i, mod - 2); FOR(i, 1, n) { c[i][0] = 1; FOR(j, 1, i) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod; } m = sz(val); FOR(i, 1, m - 1) { int len = val[i] - val[i - 1]; g[i][0] = 1; FOR(j, 1, n) g[i][j] = (g[i][j - 1] * (((j + len - 1) * inv[j]) % mod)) % mod; } } void Input(void) { cin >> n; FOR(i, 1, n) { cin >> a[i].fi >> a[i].se; val.pb(a[i].fi - 1); val.pb(a[i].se); } } void Solve(void) { Prep(); ll res = 0; FOR(i, 0, m - 1) dp[0][i] = 1; FOR(i, 1, n) { FOR(j, 1, m - 1) { if (a[i].fi <= val[j - 1] + 1 && val[j] <= a[i].se) { int cnt = 0; FOD(k, i, 1) { if (a[k].fi <= val[j - 1] + 1 && val[j] <= a[k].se) cnt++; dp[i][j] = (dp[i][j] + dp[k - 1][j - 1] * g[j][cnt]) % mod; } res = (res + dp[i][j]) % mod; } dp[i][j] = (dp[i][j] + dp[i][j - 1]) % mod; } } cout << res << endl; } signed main() { fast; if (fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } Input(); Solve(); return 0; }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
boat.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(task".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...