Submission #358477

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
358477	2021-01-25 14:33:57	CaroLinda	Boat (APIO16_boat)	C++14	100 / 100	625 ms	4588 KiB

boat

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

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] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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