Submission #49889

#TimeUsernameProblemLanguageResultExecution timeMemory
49889hamzqq9Boat (APIO16_boat)C++14
100 / 100
1296 ms3304 KiB
#include<bits/stdc++.h> #define lf double #define ll long long #define cc pair<char,char> #define ull unsigned ll #define ii pair<int,int> #define li pair<ll,int> #define iii pair<int,ii> #define iiii pair<ii,ii> #define iiii2 pair<int,iii> #define lii pair<ll,ii> #define lolo pair<ll,ll> #define heap priority_queue #define mp make_pair #define st first #define nd second #define pb push_back #define pf push_front #define ppb pop_back #define ppf pop_front #define all(x) x.begin(),x.end() #define len(x) strlen(x) #define sz(x) (int) x.size() #define orta ((bas+son)/2) #define min3(x,y,z) min(min(x,y),z) #define max3(x,y,z) max(max(x,y),z) #define umin(x,y) x=min(x,y) #define umax(x,y) x=max(x,y) #define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" " #define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar() #define MOD 1000000007 #define inf 100000000 #define M 10000002 #define N 1005 #define LOG 20 #define magic 100 #define KOK 250 #define EPS 0.0025 #define pw(x) ((1ll)<<(x)) #define PI 3.1415926535 using namespace std; int n,cev; int a[N],b[N],dp[N][N],inv[N]; vector<ii> seg,e; int add(int x,int y) { x+=y; while(x<0) x+=MOD; while(x>=MOD) x-=MOD; return x; } int mul(int x,int y) { return 1ll*x*y%MOD; } int fe(int x,int y) { if(y==0) return 1; if(y==1) return x; int res=fe(x,y/2); res=mul(res,res); if(y&1) res=mul(res,x); return res; } int main() { #if 0 freopen("input.txt","r",stdin); #endif for(int i=1;i<N;i++) { inv[i]=fe(i,MOD-2); } scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d %d",&a[i],&b[i]); e.pb({a[i],0}); e.pb({b[i],1}); } sort(all(e)); seg.pb({-inf,e[0].st-1}); for(int i=0;i<sz(e)-1;i++) { int x=e[i].st+e[i].nd,y=e[i+1].st-!e[i+1].nd; if(x>y) continue ; seg.pb({x,y}); } seg.pb({e.back().st+1,inf}); //for(auto ss:seg) printf("%d %d\n",ss.st,ss.nd); for(int i=0;i<sz(seg);i++) dp[0][i]=1; for(int i=1;i<=n;i++) { int flag=0; for(int now=0;now<sz(seg);now++) { ii rng=seg[now]; if(rng.st>b[i] || rng.nd<a[i]) { if(now) { dp[i][now]=dp[i][now-1]; } continue ; } int tot=0; int sz=rng.nd-rng.st+1; int res=sz; int ans=0; for(int j=i-1;j>=0;j--) { ans=add(ans,mul(res,dp[j][now-1])); if(rng.st>=a[j] && rng.nd<=b[j]) { tot++; res=mul(res,sz+tot); res=mul(res,inv[tot+1]); } } cev=add(cev,ans); dp[i][now]=add(dp[i][now-1],ans); //printf("RESULT : %d %d %d\n",i,now,ans); } } printf("%d",cev); }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:124:7: warning: unused variable 'flag' [-Wunused-variable]
   int flag=0;
       ^~~~
boat.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
boat.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i],&b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...