| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 117859 |
2019-06-17T09:05:16 Z |
ckodser |
Boat (APIO16_boat) |
C++14 |
|
319 ms |
8440 KB |
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);}
#define ll int
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
const ll maxn=590;
const ll mod=1e9+7;
const ll inf=1e9+9;
inline void zarb(ll &a,long long b){a=((long long)a*b)%mod;}
inline ll zarbO(long long a,long long b){return (a*b)%mod;}
inline void jam(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
inline ll jamO(ll a,ll b){a+=b;if(a>=mod)a-=mod;return a;}
ll dp[maxn][maxn*2];
ll dppar[maxn][maxn*2];
ll f[maxn*2][maxn];
ll ent[maxn][maxn];
ll rev[maxn];
ll a[maxn];
ll b[maxn];
ll poww(ll a,ll b){
ll ans=1;
while(b){
if(b&1){
zarb(ans,a);
}
b>>=1;
zarb(a,a);
}
return ans;
}
ll tmp[maxn];
void hesab(ll x,ll tol){
if(tol==1){
for(ll t=0;t+1<maxn;t++){
f[x][t]=1;
}
return ;
}
tmp[0]=1;
for(ll i=1;i<maxn;i++){
tmp[i]=zarbO(tmp[i-1],zarbO(tol-i+1,rev[i]));
}
for(ll t=0;t+1<maxn;t++){
for(ll i=0;i<=t;i++){
jam(f[x][t],zarbO(ent[t][i],tmp[i+1]));
}
}
}
int main(){
for(ll i=0;i<maxn;i++){
rev[i]=poww(i,mod-2);
}
ent[0][0]=1;
for(ll i=1;i<maxn;i++){
ent[i][0]=1;
ent[i][i]=1;
for(ll j=1;j<i;j++){
ent[i][j]=jamO(ent[i-1][j],ent[i-1][j-1]);
}
}
ll n;
cin>>n;
vector<ll> vec;
vec.pb(0);
vec.pb(inf);
for(ll i=0;i<n;i++){
cin>>a[i]>>b[i];
vec.pb(a[i]);
vec.pb(b[i]+1);
}
{
sort(vec.begin(),vec.end());
auto it=unique(vec.begin(),vec.end());
vec.resize(it-vec.begin());
}
for(ll i=0;i+1<(ll)vec.size();i++){
ll tol=vec[i+1]-vec[i];
hesab(i,tol);
}
ll ans=0;
for(ll i=0;i<n;i++){
for(ll j=0;j+1<(ll)vec.size();j++){
//dp[i][j];
if(a[i]<=vec[j] && b[i]+1>=vec[j+1]){
ll tol=vec[j+1]-vec[j];
if(tol!=1)exit(1);
//////
dp[i][j]=1;
for(ll z=i-1;z>=0;z--){
if(j)jam(dp[i][j],dppar[z][j-1]);
}
/*
ll tedad=0;
for(ll z=i-1;z>=0;z--){
if(j)jam(dp[i][j],zarbO(dppar[z][j-1],f[j][tedad]));
tedad+=(a[z]<=vec[j] && b[z]+1>=vec[j+1]);
}
jam(dp[i][j],f[j][tedad]);*/
}
}
dppar[i][0]=dp[i][0];
for(ll j=1;j+1<(ll)vec.size();j++){
dppar[i][j]=jamO(dppar[i][j-1],dp[i][j]);
}
jam(ans,dppar[i][vec.size()-2]);
}
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
224 ms |
8056 KB |
Output is correct |
| 2 |
Correct |
219 ms |
8056 KB |
Output is correct |
| 3 |
Correct |
223 ms |
8156 KB |
Output is correct |
| 4 |
Correct |
220 ms |
8064 KB |
Output is correct |
| 5 |
Correct |
223 ms |
8140 KB |
Output is correct |
| 6 |
Correct |
220 ms |
8272 KB |
Output is correct |
| 7 |
Correct |
228 ms |
8312 KB |
Output is correct |
| 8 |
Correct |
226 ms |
8288 KB |
Output is correct |
| 9 |
Correct |
236 ms |
8440 KB |
Output is correct |
| 10 |
Correct |
229 ms |
8440 KB |
Output is correct |
| 11 |
Correct |
221 ms |
8440 KB |
Output is correct |
| 12 |
Correct |
222 ms |
8312 KB |
Output is correct |
| 13 |
Correct |
218 ms |
8312 KB |
Output is correct |
| 14 |
Correct |
219 ms |
8252 KB |
Output is correct |
| 15 |
Correct |
219 ms |
8340 KB |
Output is correct |
| 16 |
Correct |
47 ms |
6392 KB |
Output is correct |
| 17 |
Correct |
48 ms |
6392 KB |
Output is correct |
| 18 |
Correct |
46 ms |
6520 KB |
Output is correct |
| 19 |
Correct |
48 ms |
6520 KB |
Output is correct |
| 20 |
Correct |
47 ms |
6520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
224 ms |
8056 KB |
Output is correct |
| 2 |
Correct |
219 ms |
8056 KB |
Output is correct |
| 3 |
Correct |
223 ms |
8156 KB |
Output is correct |
| 4 |
Correct |
220 ms |
8064 KB |
Output is correct |
| 5 |
Correct |
223 ms |
8140 KB |
Output is correct |
| 6 |
Correct |
220 ms |
8272 KB |
Output is correct |
| 7 |
Correct |
228 ms |
8312 KB |
Output is correct |
| 8 |
Correct |
226 ms |
8288 KB |
Output is correct |
| 9 |
Correct |
236 ms |
8440 KB |
Output is correct |
| 10 |
Correct |
229 ms |
8440 KB |
Output is correct |
| 11 |
Correct |
221 ms |
8440 KB |
Output is correct |
| 12 |
Correct |
222 ms |
8312 KB |
Output is correct |
| 13 |
Correct |
218 ms |
8312 KB |
Output is correct |
| 14 |
Correct |
219 ms |
8252 KB |
Output is correct |
| 15 |
Correct |
219 ms |
8340 KB |
Output is correct |
| 16 |
Correct |
47 ms |
6392 KB |
Output is correct |
| 17 |
Correct |
48 ms |
6392 KB |
Output is correct |
| 18 |
Correct |
46 ms |
6520 KB |
Output is correct |
| 19 |
Correct |
48 ms |
6520 KB |
Output is correct |
| 20 |
Correct |
47 ms |
6520 KB |
Output is correct |
| 21 |
Runtime error |
319 ms |
3748 KB |
Execution failed because the return code was nonzero |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
92 ms |
2168 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
224 ms |
8056 KB |
Output is correct |
| 2 |
Correct |
219 ms |
8056 KB |
Output is correct |
| 3 |
Correct |
223 ms |
8156 KB |
Output is correct |
| 4 |
Correct |
220 ms |
8064 KB |
Output is correct |
| 5 |
Correct |
223 ms |
8140 KB |
Output is correct |
| 6 |
Correct |
220 ms |
8272 KB |
Output is correct |
| 7 |
Correct |
228 ms |
8312 KB |
Output is correct |
| 8 |
Correct |
226 ms |
8288 KB |
Output is correct |
| 9 |
Correct |
236 ms |
8440 KB |
Output is correct |
| 10 |
Correct |
229 ms |
8440 KB |
Output is correct |
| 11 |
Correct |
221 ms |
8440 KB |
Output is correct |
| 12 |
Correct |
222 ms |
8312 KB |
Output is correct |
| 13 |
Correct |
218 ms |
8312 KB |
Output is correct |
| 14 |
Correct |
219 ms |
8252 KB |
Output is correct |
| 15 |
Correct |
219 ms |
8340 KB |
Output is correct |
| 16 |
Correct |
47 ms |
6392 KB |
Output is correct |
| 17 |
Correct |
48 ms |
6392 KB |
Output is correct |
| 18 |
Correct |
46 ms |
6520 KB |
Output is correct |
| 19 |
Correct |
48 ms |
6520 KB |
Output is correct |
| 20 |
Correct |
47 ms |
6520 KB |
Output is correct |
| 21 |
Runtime error |
319 ms |
3748 KB |
Execution failed because the return code was nonzero |
| 22 |
Halted |
0 ms |
0 KB |
- |
