Submission #257900

#TimeUsernameProblemLanguageResultExecution timeMemory
257900daniel920712Boat (APIO16_boat)C++14
0 / 100
2041 ms4352 KiB
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <set> #include <map> #include <time.h> using namespace std; long long MOD=1e9+7; map < pair < long long , long long > , long long > all; long long N; long long a[505],b[505]; map < long long , long long > con,r; set < long long > have; long long F(long long x,long long y) { long long i; if(x==0) return y!=(1e9+5); if(all.find(make_pair(x,y))!=all.end()) return all[make_pair(x,y)]; all[make_pair(x,y)]=F(x-1,y); for(auto i:con) { if(i.first>=a[x]&&r[i.first]<y&&r[i.first]<=b[x]) { all[make_pair(x,y)]+=i.second*F(x-1,i.first)%MOD; //if(i.second<0) printf("aa %lld\n",i.second); all[make_pair(x,y)]%=MOD; } } //printf("%lld %lld %lld\n",x,y,all[make_pair(x,y)]); return all[make_pair(x,y)]; } long long F2(long long x,long long y) { long long i; //printf("%lld %lld\n",x,y); if(x==0) return y!=1e9+5; if(all.find(make_pair(x,y))!=all.end()) return all[make_pair(x,y)]; all[make_pair(x,y)]=F2(x-1,y); for(i=a[x];i<=min(b[x],y-1);i++) { all[make_pair(x,y)]+=F2(x-1,i); all[make_pair(x,y)]%=MOD; } return all[make_pair(x,y)]; } int main() { //freopen("3_01.in","rt",stdin); //srand(time(NULL)); long long N,M,i; scanf("%lld",&N); for(i=1;i<=N;i++) { scanf("%lld %lld",&a[i],&b[i]); //a[i]=b[i]=rand()%100; //printf("%lld %lld\n",a[i],b[i]); have.insert(a[i]); have.insert(a[i]+1); have.insert(b[i]); have.insert(b[i]+1); } for(auto i:have) { if(i==*prev(have.end())) { con[i]=1; r[i]=i; } //printf("%lld %lld\n",*prev(have.lower_bound(i)),i); if(have.lower_bound(i)!=have.begin()) { con[*prev(have.lower_bound(i))]=i-*prev(have.lower_bound(i)); r[*prev(have.lower_bound(i))]=i-1; } } //for(auto i:con) printf("%lld %lld\n",i.first,i.second); printf("%lld\n",F(N,1e9+5)); //all.clear(); //printf("%lld\n",F2(N,1e9+5)); return 0; } /* 5 66 66 18 18 88 88 0 0 64 64 */

Compilation message (stderr)

boat.cpp: In function 'long long int F(long long int, long long int)':
boat.cpp:17:15: warning: unused variable 'i' [-Wunused-variable]
     long long i;
               ^
boat.cpp: In function 'int main()':
boat.cpp:53:17: warning: unused variable 'M' [-Wunused-variable]
     long long N,M,i;
                 ^
boat.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&N);
     ~~~~~^~~~~~~~~~~
boat.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld",&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...