oj.uz

Submission #637724

# Submission time Handle Problem Language Result Execution time Memory
637724 2022-09-02T19:43:07 Z lovrot Boat (APIO16_boat) C++11
27 / 100
 2000 ms 14852 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 14852 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 2079 ms 14852 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 13636 KB Output is correct
2 Correct 184 ms 13564 KB Output is correct
3 Correct 180 ms 13644 KB Output is correct
4 Correct 164 ms 13576 KB Output is correct
5 Correct 180 ms 13716 KB Output is correct
6 Correct 172 ms 13616 KB Output is correct
7 Correct 164 ms 13656 KB Output is correct
8 Correct 166 ms 13656 KB Output is correct
9 Correct 168 ms 13632 KB Output is correct
10 Correct 168 ms 13700 KB Output is correct
11 Correct 170 ms 13636 KB Output is correct
12 Correct 163 ms 13696 KB Output is correct
13 Correct 161 ms 13680 KB Output is correct
14 Correct 164 ms 13656 KB Output is correct
15 Correct 161 ms 13596 KB Output is correct
16 Correct 92 ms 12544 KB Output is correct
17 Correct 85 ms 12508 KB Output is correct
18 Correct 83 ms 12540 KB Output is correct
19 Correct 82 ms 12536 KB Output is correct
20 Correct 85 ms 12564 KB Output is correct

Subtask #4
0 / 42.0

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