| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 494892 |
2021-12-17T09:57:12 Z |
jamezzz |
Boat (APIO16_boat) |
C++17 |
|
200 ms |
10260 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
#define mod 1000000007
inline int add(int a,int b){
int r=a+b;
while(r>=mod)r-=mod;
while(r<0)r+=mod;
return r;
}
inline int mult(int a,int b){
return (int)(((ll)a*b)%mod);
}
inline int rd(){
int x=0;
char ch=getchar_unlocked();
while(ch<'0'||ch>'9')ch=getchar_unlocked();
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar_unlocked();
}
return x;
}
int n,m,a[505],b[505],memo[505][1005],c[1005][505],c2[505][505],w[1005][505],inv[505];
vector<int> v[1005],d;
int fp(int a,int x){
if(x==0)return 1;
int t=fp(a,x/2);
int r=mult(t,t);
if(x%2)r=mult(r,a);
return r;
}
int choose(int a,int b){
int r=1;
for(int i=a-b+1;i<=a;++i)r=mult(r,i);
for(int i=1;i<=b;++i)r=mult(r,inv[i]);
return r;
}
int dp(int i,int j){//covered up to the ith segment,now deciding for jth segment
if(i==n)return 1;
if(j==m)return (i!=0);
if(memo[i][j]!=-1)return memo[i][j];
int s=upper_bound(all(v[j]),i)-v[j].begin();
int ans=dp(i,j+1);
for(int t=s;t<sz(v[j]);++t){
ans=add(ans,mult(w[j][t-s+1],dp(v[j][t],j+1)));
}
return memo[i][j]=ans;
}
main(){
sf("%lld",&n);
for(int i=1;i<=n;++i){
sf("%lld%lld",&a[i],&b[i]);
d.pb(a[i]),d.pb(b[i]);
}
disc(d);m=sz(d);d.pb(d.back()+1);
for(int i=1;i<=n;++i){
for(int j=0;j<m;++j){
if(a[i]<=d[j]&&d[j]<=b[i])v[j].pb(i);
}
}
for(int i=1;i<=n;++i)inv[i]=fp(i,mod-2);
for(int i=0;i<m;++i){
int a=d[i+1]-d[i];
for(int b=1;b<=sz(v[i]);++b){
c[i][b]=choose(a,b);
}
}
for(int i=1;i<=n;++i){
for(int j=0;j<=i;++j){
c2[i][j]=choose(i,j);
}
}
for(int i=0;i<m;++i){
int a=d[i+1]-d[i];
for(int b=1;b<=sz(v[i]);++b){
for(int k=0;k<b;++k){
w[i][b]=add(w[i][b],mult(c[i][k+1],c2[b][k]));
}
}
}
memset(memo,-1,sizeof memo);
pf("%lld\n",dp(0,0));
}
/*
2
1 2
2 3
*/
Compilation message
boat.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
89 | main(){
| ^~~~
boat.cpp: In function 'int main()':
boat.cpp:114:7: warning: unused variable 'a' [-Wunused-variable]
114 | int a=d[i+1]-d[i];
| ^
boat.cpp:90:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | sf("%lld",&n);
| ^
boat.cpp:92:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | sf("%lld%lld",&a[i],&b[i]);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
10260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
10260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
6348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
200 ms |
10260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
