Submission #723249

#TimeUsernameProblemLanguageResultExecution timeMemory
723249n0sk1llBoat (APIO16_boat)C++14
0 / 100
3 ms360 KiB
#include <bits/stdc++.h> #define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0) #define mp make_pair #define xx first #define yy second #define pb push_back #define pf push_front #define popb pop_back #define popf pop_front #define all(x) x.begin(),x.end() #define ff(i,a,b) for (int i = a; i < b; i++) #define fff(i,a,b) for (int i = a; i <= b; i++) #define bff(i,a,b) for (int i = b-1; i >= a; i--) #define bfff(i,a,b) for (int i = b; i >= a; i--) using namespace std; long double typedef ld; unsigned int typedef ui; long long int typedef li; pair<int,int> typedef pii; pair<li,li> typedef pli; pair<ld,ld> typedef pld; vector<vector<int>> typedef graph; unsigned long long int typedef ull; //const int mod = 998244353; const int mod = 1000000007; //Note to self: Check for overflow int inv[2005]; int power(int a, int n) { li c=1; while (n) { if (n&1) (c*=a)%=mod; a=(li)a*a%mod,n>>=1; } return c; } int a[505],b[505]; int dp[505]; int main() { FAST; int n; cin>>n; fff(i,1,n) cin>>a[i]>>b[i]; vector<int> kords; kords.pb(0); kords.pb(mod); fff(i,1,n) kords.pb(a[i]); fff(i,1,n) kords.pb(b[i]+1); sort(all(kords)); kords.erase(unique(all(kords)),kords.end()); dp[0]=1; fff(i,1,2000) inv[i]=power(i,mod-2); inv[0]=1; ff(k,1,(int)kords.size()-1) { bfff(i,1,n) if (a[i]<=kords[k] && kords[k]<=b[i]) { int binom=1,gore=kords[k+1]-kords[k],dole=0; bfff(f,1,i) { if (a[f]<=kords[k] && kords[k]<=b[f]) { (binom*=(gore++))%=mod; (binom*=(inv[++dole]))%=mod; } (dp[i]+=(li)dp[f-1]*binom)%=mod; } } //cout<<kords[k]<<": "; //fff(i,1,n) cout<<dp[i]<<" "; cout<<endl; } int ans=0; fff(i,1,n) (ans+=dp[i])%=mod; cout<<ans<<"\n"; } //Note to self: Check for overflow
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...