| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 358477 |
2021-01-25T14:33:57 Z |
CaroLinda |
Boat (APIO16_boat) |
C++14 |
|
625 ms |
4588 KB |
#include <bits/stdc++.h>
#define debug printf
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) x.size()
const int MAXN = 1010 ;
const ll MOD = 1e9+7 ;
using namespace std ;
/* Quick description of the solution because I'm dumb and disorganized */
//dp[i][j] represents the possibilities given that I only have the boats [1;i] and the intervals [1;j]
//and is guaranteed that boat number i is going to be chosen
//For this problem, I had to come up with a little lemma (don't know if it is a well-known fact)
//(I don't do Math olympiads :P)
//Link to the "proof": https://pasteboard.co/JLhIM6E.jpg
//To find C(x+y, y) quickly, I did a trick:
//C(x+y,y) = C(x+y-1,y-1) * (x+y)/y
//Because the inverses of 1, 2, ..., y are easily calculated in O(N)
int N , M ;
int A[MAXN] , B[MAXN] ;
int val[MAXN] ;
ll inv[MAXN] ;
ll dp[MAXN][MAXN] ;
int main()
{
vector<int> compression ;
inv[1] = 1 ;
scanf("%d", &N ) ;
for(int i = 1 ; i <= N ; i++ )
{
scanf("%d %d", &A[i], &B[i] ) ;
compression.push_back(A[i]) ;
compression.push_back( ++B[i] ) ;
if( i > 1 )
{
inv[i] = ( (-MOD/i)*inv[MOD%i] ) % MOD ;
if(inv[i] < 0 ) inv[i] += MOD ;
}
}
sort(all(compression) ) ;
compression.erase( unique(all(compression) ) , compression.end() ) ;
M = sz(compression) ;
for(int i = 0 ; i < M-1 ; i++ ) val[i+1] = compression[i+1] - compression[i] ;
for(int i= 1 ; i <= N ; i++ )
{
A[i] = lower_bound(all(compression) , A[i] ) - compression.begin() +1 ;
B[i] = lower_bound(all(compression) , B[i] ) - compression.begin() + 1 ;
}
for(int j = 0 ; j < M ; j++ ) dp[0][j] = 1LL ;
ll ans = 0LL ;
for(int i = 1; i <= N ; i++ )
{
for(int j = A[i] ; j < B[i] ; j++ )
{
//In the beginning, cnt is C(val[j]+0, 0+1)
ll cnt = val[j] , y = 1 ;
ll x = val[j] ;
for(int person = i-1 ; person >= 0 ; person-- )
{
dp[i][j] += (cnt * dp[person][j-1] ) % MOD ;
if( dp[i][j] >= MOD ) dp[i][j] -= MOD ;
if( A[person] <= j && B[person] > j )
{
++x , ++y ;
cnt = ( ( cnt * x ) % MOD * inv[y] ) % MOD ;
}
}
}
for(int j = 1 ; j < M ; j++ )
{
dp[i][j] += dp[i][j-1] ;
if( dp[i][j] >= MOD ) dp[i][j] -= MOD ;
}
ans += dp[i][M-1] ;
if(ans >= MOD ) ans -= MOD ;
}
printf("%lld\n", ans ) ;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
36 | scanf("%d", &N ) ;
| ~~~~~^~~~~~~~~~~
boat.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
39 | scanf("%d %d", &A[i], &B[i] ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 3 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 4 |
Correct |
9 ms |
4460 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 6 |
Correct |
6 ms |
4332 KB |
Output is correct |
| 7 |
Correct |
6 ms |
4332 KB |
Output is correct |
| 8 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 9 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 10 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 11 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 12 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 13 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 14 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 15 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 16 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 17 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 3 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 4 |
Correct |
9 ms |
4460 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 6 |
Correct |
6 ms |
4332 KB |
Output is correct |
| 7 |
Correct |
6 ms |
4332 KB |
Output is correct |
| 8 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 9 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 10 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 11 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 12 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 13 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 14 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 15 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 16 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 17 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 21 |
Correct |
309 ms |
4396 KB |
Output is correct |
| 22 |
Correct |
317 ms |
4380 KB |
Output is correct |
| 23 |
Correct |
255 ms |
4332 KB |
Output is correct |
| 24 |
Correct |
303 ms |
4332 KB |
Output is correct |
| 25 |
Correct |
277 ms |
4332 KB |
Output is correct |
| 26 |
Correct |
512 ms |
4304 KB |
Output is correct |
| 27 |
Correct |
540 ms |
4408 KB |
Output is correct |
| 28 |
Correct |
520 ms |
4460 KB |
Output is correct |
| 29 |
Correct |
519 ms |
4376 KB |
Output is correct |
| 30 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 31 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 32 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 33 |
Correct |
8 ms |
4460 KB |
Output is correct |
| 34 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 35 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 36 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 37 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 38 |
Correct |
8 ms |
4332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
876 KB |
Output is correct |
| 2 |
Correct |
3 ms |
876 KB |
Output is correct |
| 3 |
Correct |
3 ms |
876 KB |
Output is correct |
| 4 |
Correct |
3 ms |
876 KB |
Output is correct |
| 5 |
Correct |
4 ms |
876 KB |
Output is correct |
| 6 |
Correct |
6 ms |
876 KB |
Output is correct |
| 7 |
Correct |
5 ms |
876 KB |
Output is correct |
| 8 |
Correct |
6 ms |
876 KB |
Output is correct |
| 9 |
Correct |
6 ms |
876 KB |
Output is correct |
| 10 |
Correct |
6 ms |
876 KB |
Output is correct |
| 11 |
Correct |
3 ms |
876 KB |
Output is correct |
| 12 |
Correct |
3 ms |
876 KB |
Output is correct |
| 13 |
Correct |
3 ms |
876 KB |
Output is correct |
| 14 |
Correct |
3 ms |
876 KB |
Output is correct |
| 15 |
Correct |
3 ms |
876 KB |
Output is correct |
| 16 |
Correct |
2 ms |
876 KB |
Output is correct |
| 17 |
Correct |
2 ms |
876 KB |
Output is correct |
| 18 |
Correct |
2 ms |
876 KB |
Output is correct |
| 19 |
Correct |
2 ms |
876 KB |
Output is correct |
| 20 |
Correct |
3 ms |
876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 2 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 3 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 4 |
Correct |
9 ms |
4460 KB |
Output is correct |
| 5 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 6 |
Correct |
6 ms |
4332 KB |
Output is correct |
| 7 |
Correct |
6 ms |
4332 KB |
Output is correct |
| 8 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 9 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 10 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 11 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 12 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 13 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 14 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 15 |
Correct |
7 ms |
4332 KB |
Output is correct |
| 16 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 17 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 18 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 19 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 20 |
Correct |
4 ms |
3052 KB |
Output is correct |
| 21 |
Correct |
309 ms |
4396 KB |
Output is correct |
| 22 |
Correct |
317 ms |
4380 KB |
Output is correct |
| 23 |
Correct |
255 ms |
4332 KB |
Output is correct |
| 24 |
Correct |
303 ms |
4332 KB |
Output is correct |
| 25 |
Correct |
277 ms |
4332 KB |
Output is correct |
| 26 |
Correct |
512 ms |
4304 KB |
Output is correct |
| 27 |
Correct |
540 ms |
4408 KB |
Output is correct |
| 28 |
Correct |
520 ms |
4460 KB |
Output is correct |
| 29 |
Correct |
519 ms |
4376 KB |
Output is correct |
| 30 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 31 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 32 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 33 |
Correct |
8 ms |
4460 KB |
Output is correct |
| 34 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 35 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 36 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 37 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 38 |
Correct |
8 ms |
4332 KB |
Output is correct |
| 39 |
Correct |
3 ms |
876 KB |
Output is correct |
| 40 |
Correct |
3 ms |
876 KB |
Output is correct |
| 41 |
Correct |
3 ms |
876 KB |
Output is correct |
| 42 |
Correct |
3 ms |
876 KB |
Output is correct |
| 43 |
Correct |
4 ms |
876 KB |
Output is correct |
| 44 |
Correct |
6 ms |
876 KB |
Output is correct |
| 45 |
Correct |
5 ms |
876 KB |
Output is correct |
| 46 |
Correct |
6 ms |
876 KB |
Output is correct |
| 47 |
Correct |
6 ms |
876 KB |
Output is correct |
| 48 |
Correct |
6 ms |
876 KB |
Output is correct |
| 49 |
Correct |
3 ms |
876 KB |
Output is correct |
| 50 |
Correct |
3 ms |
876 KB |
Output is correct |
| 51 |
Correct |
3 ms |
876 KB |
Output is correct |
| 52 |
Correct |
3 ms |
876 KB |
Output is correct |
| 53 |
Correct |
3 ms |
876 KB |
Output is correct |
| 54 |
Correct |
2 ms |
876 KB |
Output is correct |
| 55 |
Correct |
2 ms |
876 KB |
Output is correct |
| 56 |
Correct |
2 ms |
876 KB |
Output is correct |
| 57 |
Correct |
2 ms |
876 KB |
Output is correct |
| 58 |
Correct |
3 ms |
876 KB |
Output is correct |
| 59 |
Correct |
325 ms |
4324 KB |
Output is correct |
| 60 |
Correct |
327 ms |
4408 KB |
Output is correct |
| 61 |
Correct |
314 ms |
4332 KB |
Output is correct |
| 62 |
Correct |
315 ms |
4296 KB |
Output is correct |
| 63 |
Correct |
312 ms |
4588 KB |
Output is correct |
| 64 |
Correct |
595 ms |
4424 KB |
Output is correct |
| 65 |
Correct |
600 ms |
4416 KB |
Output is correct |
| 66 |
Correct |
625 ms |
4332 KB |
Output is correct |
| 67 |
Correct |
609 ms |
4332 KB |
Output is correct |
| 68 |
Correct |
598 ms |
4464 KB |
Output is correct |
| 69 |
Correct |
244 ms |
4332 KB |
Output is correct |
| 70 |
Correct |
246 ms |
4332 KB |
Output is correct |
| 71 |
Correct |
254 ms |
4460 KB |
Output is correct |
| 72 |
Correct |
253 ms |
4332 KB |
Output is correct |
| 73 |
Correct |
263 ms |
4332 KB |
Output is correct |
| 74 |
Correct |
72 ms |
3052 KB |
Output is correct |
| 75 |
Correct |
67 ms |
3200 KB |
Output is correct |
| 76 |
Correct |
66 ms |
3180 KB |
Output is correct |
| 77 |
Correct |
63 ms |
3052 KB |
Output is correct |
| 78 |
Correct |
66 ms |
3052 KB |
Output is correct |
