Submission #518472

#TimeUsernameProblemLanguageResultExecution timeMemory
518472julian33Boat (APIO16_boat)C++14
9 / 100
900 ms4468 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mxN=2e5+5; //make sure this is right const int mod=1e9+7; struct RANK{ vector<int> all; int get(int x){return lower_bound(all.begin(),all.end(),x)-all.begin()+1;} void add(int x){all.pb(x);} void fix(){ sort(all.begin(),all.end()); all.resize(unique(all.begin(),all.end())-all.begin()); } } rnk; ll dp[505][1005],a[505],b[505]; int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif rnk.add(1); int n; cin>>n; int mx=0; for(int i=1;i<=n;i++){ cin>>a[i]>>b[i]; rnk.add(a[i]); rnk.add(b[i]); maxa(mx,(int)b[i]); } rnk.add(mx+1); rnk.fix(); dp[0][1]=1; for(int i=1;i<=n;i++){ int A=a[i]; int B=b[i]; for(int j=1;j<=sz(rnk.all);j++){ ll ways=min(B,rnk.all[j-1]-1)-max(A,j==1?1:rnk.all[j-2])+1; maxa(ways,0LL); dp[i][j]=dp[i-1][j]; for(int k=j-1;k>=1;k--){ dp[i][j]+=(dp[i-1][k]*ways)%mod; dp[i][j]%=mod; } } } ll ans=0; for(int i=1;i<=sz(rnk.all);i++) ans=(ans+dp[n][i])%mod; cout<<(ans-1+mod)%mod<<"\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...