oj.uz

Submission #184086

# Submission time Handle Problem Language Result Execution time Memory
184086 2020-01-10T13:00:24 Z dndhk Boat (APIO16_boat) C++14
0 / 100
 2000 ms 11348 KB 
#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const ll MOD = 1000000007;
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 500;

int N, M;
int a[MAX_N+1], b[MAX_N+1];
vector<int> v1;
vector<ll> v;
map<int, int> mp;

void input(){
	scanf("%d", &N);
	for(int i=1 ;i<=N; i++){
		scanf("%d%d", &a[i], &b[i]);
		b[i]++;
		v1.pb(a[i]); v1.pb(b[i]);
	}
	sort(v1.begin(), v1.end());
	v1.erase(unique(v1.begin(), v1.end()), v1.end());
	sort(v1.begin(), v1.end());
	v.pb(1LL);
	for(int i=0; i<v1.size()-1; i++){
		mp[v1[i]] = v.size();
		v.pb(v1[i+1]-v1[i]);
	}mp[v1.back()] = v.size();
	for(int i=1; i<=N; i++){
		a[i] = mp[a[i]]; b[i] = mp[b[i]]-1;
	}
	M = v.size()-1;
}

ll multi(ll x, ll y){
	if(y==0){
		return 1LL;
	}if(y==1){
		return x%MOD;
	}
	ll m = multi(x, y/2);
	if(y%2){
		return ((m*m%MOD)*x)%MOD;
	}
	return (m*m)%MOD;
}

ll inv[MAX_N+1];

ll dp[MAX_N+1][MAX_N*2+1];
ll dp2[MAX_N+1][MAX_N+1];

void solve(){
	for(int i=1; i<=N; i++){
		inv[i] = multi((ll)i, MOD-2);
	}
	for(int i=0; i<=M; i++)	dp[0][i] = 1LL;
	for(int i=1; i<=N; i++)	dp[i][0] = 1LL;	
	for(int k=1; k<=M; k++){
		for(int i=1; i<=N; i++){
			dp2[i][1] = dp2[i-1][1];
			if(a[i]<=k && k<=b[i]) dp2[i][1] = (dp2[i][1] + dp[i-1][k-1]) % MOD;
			dp[i][k]=dp2[i][1];
			for(int j=2; j<=N; j++){
				dp2[i][j] = 0LL;
				if(a[i]<=k && k<=b[i]) dp2[i][j] = (dp2[i-1][j-1] * (max(0LL, v[k]-(ll)(j-1)))%MOD) * inv[j] % MOD;
				dp2[i][j] = (dp2[i][j] + dp2[i-1][j]) % MOD;
				dp[i][k] = (dp[i][k] + dp2[i][j]) % MOD;
			}
			dp[i][k] = (dp[i][k] + dp[i][k-1]) % MOD;
		}
		cout<<k<<endl;
		for(int i=1; i<=N; i++){
			for(int j=1; j<=N; j++){
				cout<<i<<" "<<j<<" "<<dp2[i][j]<<endl;
			}
		}
	}
	
	for(int i=1; i<=N; i++){
		for(int j=0; j<=M; j++){
			cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
		}
	}
}

int main(){
	input();
	solve();
	cout<<(dp[N][M]+MOD-1) % MOD;
	return 0;
}

Compilation message

boat.cpp: In function 'void input()':
boat.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v1.size()-1; i++){
               ~^~~~~~~~~~~~
boat.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
boat.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2008 ms 11348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2008 ms 11348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 7884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2008 ms 11348 KB Time limit exceeded
2 Halted 0 ms 0 KB -