| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 110581 |
2019-05-11T09:00:12 Z |
Pro_ktmr |
Boat (APIO16_boat) |
C++14 |
|
724 ms |
8620 KB |
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define PB push_back
#define MP make_pair
const LL MOD = 1000000007;
//累乗 O(log N)
long long power(long long x, int N){
if(N == 1) return x;
long long tmp = power(x, N/2);
if(N%2 == 0) return tmp * tmp % MOD;
else return tmp * tmp % MOD * x % MOD;
}
//逆元 O(log x)
long long inverse(long long x){
return power(x, MOD-2);
}
//コンビネーション
struct Combination{
private:
int N;
vector<long long> fact, inv;
public:
void init(int n){ //初期化する O(N)
N = n;
fact.push_back(1);
inv.push_back(1);
for(long long i=1; i<=N; i++){
fact.push_back(fact.back()*i%MOD);
inv.push_back(inverse(fact.back()));
}
}
long long comb(int n, int k){ //nCkを求める O(1)
return fact[n] * inv[k] % MOD* inv[n-k] % MOD;
}
};
Combination comb;
int N, a[500], b[500], A[500], B[500];
vector<int> v;
vector<int> ls[1000];
LL culc(LL range, int num){
if(num == 1) return range;
LL ret = 0;
LL tmp1 = range;
LL tmp2 = range-1;
for(int i=0; i<=num-2 && tmp2 > 0; i++){ //中のを何個使うか
tmp1 = tmp1 * tmp2 % MOD;
tmp2--;
ret += tmp2 * comb.comb(num-2, i) % MOD;
}
return ret;
}
//a:=区間、b:=学校
LL dp[1000][500][2];
LL solve(int a, int b, int ok){
if(a == v.size()-1) return 1;
if(ok == 0 && b == N) return 0;
if(ok == 1 && b == N) return 1;
if(dp[a][b][ok] != -1) return dp[a][b][ok];
if(ok == 0){
dp[a][b][ok] = solve(a, b+1, 0);
if(A[b] <= a && a < B[b]){
int idx = lower_bound(ls[a].begin(), ls[a].end(), b) - ls[a].begin();
LL range = v[a+1] - v[a];
for(int i=idx; i<ls[a].size()-1; i++){
dp[a][b][ok] += culc(range, i-idx+1)*solve(a+1, ls[a][i]+1, 1);
dp[a][b][ok] %= MOD;
}
}
}
else{
dp[a][b][ok] = solve(a+1, b, 1);
dp[a][b][ok] += solve(a, b, 0);
dp[a][b][ok] %= MOD;
}
return dp[a][b][ok];
}
int main(){
scanf("%d", &N);
for(int i=0; i<N; i++){
scanf("%d%d", a+i, b+i);
b[i]++;
v.PB(a[i]);
v.PB(b[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int i=0; i<N; i++){
A[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
B[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin();
for(int j=A[i]; j<B[i]; j++) ls[j].PB(i);
}
for(int i=0; i<v.size(); i++){
ls[i].PB(N);
for(int j=0; j<N; j++) dp[i][j][0] = -1;
for(int j=0; j<N; j++) dp[i][j][1] = -1;
}
comb.init(N);
printf("%d\n", (solve(0, 0, 1)-1+MOD)%MOD);
}
Compilation message
boat.cpp: In function 'long long int solve(int, int, int)':
boat.cpp:64:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a == v.size()-1) return 1;
~~^~~~~~~~~~~~~
boat.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=idx; i<ls[a].size()-1; i++){
~^~~~~~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:102:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
boat.cpp:108:43: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
printf("%d\n", (solve(0, 0, 1)-1+MOD)%MOD);
~~~~~~~~~~~~~~~~~~~~~~~~~~^
boat.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
boat.cpp:90: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);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
8448 KB |
Output is correct |
| 2 |
Correct |
22 ms |
8448 KB |
Output is correct |
| 3 |
Correct |
23 ms |
8448 KB |
Output is correct |
| 4 |
Correct |
30 ms |
8448 KB |
Output is correct |
| 5 |
Correct |
32 ms |
8448 KB |
Output is correct |
| 6 |
Correct |
20 ms |
8448 KB |
Output is correct |
| 7 |
Correct |
19 ms |
8320 KB |
Output is correct |
| 8 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 9 |
Correct |
18 ms |
8448 KB |
Output is correct |
| 10 |
Correct |
20 ms |
8448 KB |
Output is correct |
| 11 |
Correct |
20 ms |
8376 KB |
Output is correct |
| 12 |
Correct |
27 ms |
8320 KB |
Output is correct |
| 13 |
Correct |
21 ms |
8448 KB |
Output is correct |
| 14 |
Correct |
27 ms |
8448 KB |
Output is correct |
| 15 |
Correct |
24 ms |
8448 KB |
Output is correct |
| 16 |
Correct |
8 ms |
1792 KB |
Output is correct |
| 17 |
Correct |
8 ms |
1920 KB |
Output is correct |
| 18 |
Correct |
8 ms |
1920 KB |
Output is correct |
| 19 |
Correct |
8 ms |
1920 KB |
Output is correct |
| 20 |
Correct |
6 ms |
1920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
8448 KB |
Output is correct |
| 2 |
Correct |
22 ms |
8448 KB |
Output is correct |
| 3 |
Correct |
23 ms |
8448 KB |
Output is correct |
| 4 |
Correct |
30 ms |
8448 KB |
Output is correct |
| 5 |
Correct |
32 ms |
8448 KB |
Output is correct |
| 6 |
Correct |
20 ms |
8448 KB |
Output is correct |
| 7 |
Correct |
19 ms |
8320 KB |
Output is correct |
| 8 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 9 |
Correct |
18 ms |
8448 KB |
Output is correct |
| 10 |
Correct |
20 ms |
8448 KB |
Output is correct |
| 11 |
Correct |
20 ms |
8376 KB |
Output is correct |
| 12 |
Correct |
27 ms |
8320 KB |
Output is correct |
| 13 |
Correct |
21 ms |
8448 KB |
Output is correct |
| 14 |
Correct |
27 ms |
8448 KB |
Output is correct |
| 15 |
Correct |
24 ms |
8448 KB |
Output is correct |
| 16 |
Correct |
8 ms |
1792 KB |
Output is correct |
| 17 |
Correct |
8 ms |
1920 KB |
Output is correct |
| 18 |
Correct |
8 ms |
1920 KB |
Output is correct |
| 19 |
Correct |
8 ms |
1920 KB |
Output is correct |
| 20 |
Correct |
6 ms |
1920 KB |
Output is correct |
| 21 |
Incorrect |
724 ms |
8620 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
1664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
8448 KB |
Output is correct |
| 2 |
Correct |
22 ms |
8448 KB |
Output is correct |
| 3 |
Correct |
23 ms |
8448 KB |
Output is correct |
| 4 |
Correct |
30 ms |
8448 KB |
Output is correct |
| 5 |
Correct |
32 ms |
8448 KB |
Output is correct |
| 6 |
Correct |
20 ms |
8448 KB |
Output is correct |
| 7 |
Correct |
19 ms |
8320 KB |
Output is correct |
| 8 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 9 |
Correct |
18 ms |
8448 KB |
Output is correct |
| 10 |
Correct |
20 ms |
8448 KB |
Output is correct |
| 11 |
Correct |
20 ms |
8376 KB |
Output is correct |
| 12 |
Correct |
27 ms |
8320 KB |
Output is correct |
| 13 |
Correct |
21 ms |
8448 KB |
Output is correct |
| 14 |
Correct |
27 ms |
8448 KB |
Output is correct |
| 15 |
Correct |
24 ms |
8448 KB |
Output is correct |
| 16 |
Correct |
8 ms |
1792 KB |
Output is correct |
| 17 |
Correct |
8 ms |
1920 KB |
Output is correct |
| 18 |
Correct |
8 ms |
1920 KB |
Output is correct |
| 19 |
Correct |
8 ms |
1920 KB |
Output is correct |
| 20 |
Correct |
6 ms |
1920 KB |
Output is correct |
| 21 |
Incorrect |
724 ms |
8620 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
