oj.uz

Submission #117829

# Submission time Handle Problem Language Result Execution time Memory
117829 2019-06-17T08:33:36 Z ckodser Boat (APIO16_boat) C++14
27 / 100
 438 ms 11624 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=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];
ll dppar[maxn][maxn];
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){
	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(){
	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]=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 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]=(dppar[i][j-1]+dp[i][j])%mod;
		}
		jam(ans,dppar[i][vec.size()-2]);
	}
	cout<<ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 438 ms 11624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 438 ms 11624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 4908 KB Output is correct
2 Correct 91 ms 4912 KB Output is correct
3 Correct 98 ms 4988 KB Output is correct
4 Correct 96 ms 4948 KB Output is correct
5 Correct 94 ms 4856 KB Output is correct
6 Correct 95 ms 4856 KB Output is correct
7 Correct 95 ms 4984 KB Output is correct
8 Correct 96 ms 4956 KB Output is correct
9 Correct 94 ms 4984 KB Output is correct
10 Correct 94 ms 4992 KB Output is correct
11 Correct 92 ms 4984 KB Output is correct
12 Correct 101 ms 4884 KB Output is correct
13 Correct 94 ms 4956 KB Output is correct
14 Correct 94 ms 4956 KB Output is correct
15 Correct 96 ms 4896 KB Output is correct
16 Correct 66 ms 4600 KB Output is correct
17 Correct 56 ms 4472 KB Output is correct
18 Correct 58 ms 4640 KB Output is correct
19 Correct 56 ms 4472 KB Output is correct
20 Correct 53 ms 4472 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 438 ms 11624 KB Output isn't correct
2 Halted 0 ms 0 KB -