Submission #251788

#TimeUsernameProblemLanguageResultExecution timeMemory
251788hackermubBoat (APIO16_boat)C++17
9 / 100
392 ms524292 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fi first #define se second #define all(v) v.begin(),v.end() #define pb push_back #define sz(v) (int)v.size() const int MOD = 1e9+7; const int64_t INF = 1e18; int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(); //If you hack my code , You are gay; int n; cin>>n; vector<int> L(n),R(n); vector<int> v={0}; for(int i=0;i<n;i++){ cin>>L[i]>>R[i]; for(int j=L[i];j<=R[i];j++){ v.push_back(j); } } sort(all(v)); v.erase(unique(all(v)),v.end()); for(int i=0;i<n;i++){ L[i] = lower_bound(all(v),L[i])-v.begin(); R[i] = lower_bound(all(v),R[i])-v.begin(); //cout<<L[i]<<" "<<R[i]<<"\n"; } vector<vector<int>> dp(n+1,vector<int>(sz(v)+1,0)),sum(n+1,vector<int>(sz(v)+1,0)); dp[0][0]=1; for(int i=0;i<sz(v);i++) sum[0][i] = 1; for(int i=1;i<=n;i++){ for(int j=L[i-1];j<=R[i-1];j++){ dp[i][j] = (dp[i][j] + sum[i-1][j-1])%MOD; } sum[i][0] = 1; for(int j=1;j<sz(v);j++){ sum[i][j] = (dp[i][j] + sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1])%MOD; } } cout<<(sum[n][sz(v)-1]-1+MOD)%MOD; 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...