Submission #637724

#	Time	Username	Problem	Language	Result	Execution time	Memory
637724		lovrot	Boat (APIO16_boat)	C++11	27 / 100	2079 ms	14852 KiB

boat

#include <bits/stdc++.h> 

#define ll long long
#define pii pair<ll, ll> 
#define X first
#define Y second
#define pb push_back

using namespace std; 

const int N = 1010;
const ll MOD = 1e9 + 7;

ll n, intcnt, l[N], r[N];
ll siz[N], fact[N], povrh[N][N], calc[N][N];
ll dp[N][N];

int u[N][N];

vector<pii> intv;
vector<ll> v;

ll add(ll a, ll b){ 
	return (a + b >= MOD ? a + b - MOD : a + b);
}

ll mult(ll a, ll b){ 
	return a * b % MOD;
}

ll fastpow(ll b, ll e){ 
	ll ret = 1;
	while(e){
		if(e & 1) ret = mult(ret, b);
		b = mult(b, b);
		e >>= 1;
	}
	return ret;
}

ll divd(ll a, ll b){ 
	return mult(a, fastpow(b, MOD - 2));
}

void precompute(){ 
	fact[0] = 1;
	for(int i = 1; i < N; i++) fact[i] = mult(fact[i - 1], i);
	for(int i = 0; i < N / 2; i++) for(int j = 0; j <= i; j++) povrh[i][j] = divd(fact[i], mult(fact[j], fact[i - j]));
	
	for(int i = 0; i < intcnt; i++){
		ll sfact = 1; 
		for(ll k = 1; k <= n; k++){ 
			ll sfact = 1;
			for(ll j = 1; j <= min(k, siz[i]); j++){ 
				sfact = mult(sfact, siz[i] - j + 1);
				calc[i][k] = add(calc[i][k], mult(povrh[k - 1][j - 1], divd(sfact, fact[j])));
			}
		}
	}
}

ll DP(int x, int b){ 
	if(b >= intcnt) return 1;
	if(dp[x][b] != -1) return dp[x][b];

	dp[x][b] = DP(x, b + 1);

	int cnt = 0;
	for(int i = x; i < n; i++){ 
		cnt += u[i][b];
		if(u[i][b]) dp[x][b] = add(dp[x][b], mult(calc[b][cnt], DP(i + 1, b + 1)));
	}

	// printf("%d %lld %lld s: %lld\n", x, b, dp[x][b], calc[b][2]);
	return dp[x][b];
}

int main(){ 
	for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) dp[i][j] = -1;

	scanf("%d", &n);

	for(int i = 0; i < n; i++){ 
		scanf("%lld%lld", &l[i], &r[i]);
		v.pb(l[i]);
		v.pb(r[i]);
	}

	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());

	for(int i = 0; i < v.size(); i++){ 
		if(i != 0 && v[i - 1] < v[i] - 1){ 
			intv.pb({v[i - 1] + 1, v[i] - 1});
		}
		intv.pb({v[i], v[i]});
	}

	intcnt = intv.size();
 
	for(int i = 0; i < intcnt; i++) siz[i] = intv[i].Y - intv[i].X + 1;

	for(int i = 0; i < n; i++){
		for(ll j = 0; j < intcnt; j++){ 
			if(intv[j].X >= l[i] && intv[j].Y <= r[i]){ 
				u[i][j] = true;
			}
		}
		// printf("%d %d %d\n", i, poc[i], kraj[i]);
	}

	precompute();
	
	printf("%lld\n", add(DP(0, 0), MOD - 1));
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void precompute()':
boat.cpp:51:6: warning: unused variable 'sfact' [-Wunused-variable]
   51 |   ll sfact = 1;
      |      ^~~~~
boat.cpp: In function 'int main()':
boat.cpp:81:10: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   81 |  scanf("%d", &n);
      |         ~^   ~~
      |          |   |
      |          |   long long int*
      |          int*
      |         %lld
boat.cpp:92:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 0; i < v.size(); i++){
      |                 ~~^~~~~~~~~~
boat.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
boat.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%lld%lld", &l[i], &r[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42