| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 117801 |
2019-06-17T08:06:35 Z |
ckodser |
Boat (APIO16_boat) |
C++14 |
|
334 ms |
7844 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 long long
#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=510;
const ll inf=1e9+800;
const ll mod=1e9+7;
inline ll zarb(ll a,ll b){return (a*b)%mod;}
inline void jam(ll &a,ll b){a+=b;if(a>=mod)a-=mod;}
ll dp[maxn][maxn];
ll dppar[maxn][maxn];
ll f[maxn][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){
ans=(ans*a)%mod;
}
b>>=1;
a=(a*a)%mod;
}
return ans;
}
ll tmp[maxn];
void hesab(ll x,ll tol){
tmp[0]=1;
for(ll i=1;i<maxn;i++){
tmp[i]=zarb(tmp[i-1],zarb(tol-i+1,rev[i]));
}
for(ll t=0;t<maxn;t++){
for(ll i=0;i<=t;i++){
jam(f[x][t],zarb(ent[t][i],tmp[i+1]));
}
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
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]=(ent[i-1][j]+ent[i-1][j-1])%mod;
}
}
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(auto e:vec)cout<<e<<' ';cout<<endl;
for(ll i=0;i+1<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<vec.size();j++){
//dp[i][j];
if(a[i]<=vec[j] && b[i]+1>=vec[j+1]){
ll tol=vec[j+1]-vec[j];
dp[i][j]=tol;
ll tedad=0;
for(ll z=i-1;z>=0;z--){
// cout<<j<<"^"<<tedad<<":"<<f[j][tedad]<<endl;
jam(dp[i][j],zarb(dppar[z][j-1],f[j][tedad]));
tedad+=(a[z]<=vec[j] && b[z]+1>=vec[j+1]);
}
}
}
// for(ll j=0;j+1<vec.size();j++)cout<<dp[i][j]<<' ';cout<<endl;
dppar[i][0]=dp[i][0];
for(ll j=1;j+1<vec.size();j++){
dppar[i][j]=(dppar[i][j-1]+dp[i][j])%mod;
}
jam(ans,dppar[i][vec.size()-2]);
}
cout<<ans;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:136:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i=0;i+1<vec.size();i++){
~~~^~~~~~~~~~~
boat.cpp:142:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=0;j+1<vec.size();j++){
~~~^~~~~~~~~~~
boat.cpp:157:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll j=1;j+1<vec.size();j++){
~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
334 ms |
7844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
334 ms |
7844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
3944 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
334 ms |
7844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
