oj.uz

답안 #117859

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
117859 2019-06-17T09:05:16 Z ckodser Boat (APIO16_boat) C++14
9 / 100
 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;
}

Subtask #1
9.0 / 9.0

# 결과 실행 시간 메모리 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

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 92 ms 2168 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 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 -