| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 110591 |
2019-05-11T09:18:55 Z |
Pro_ktmr |
Boat (APIO16_boat) |
C++14 |
|
28 ms |
8440 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; i++){ //中のを何個使うか
if(tmp2 == 0) break;
tmp1 = tmp1 * tmp2 % MOD;
tmp1 = tmp1 * inverse(i+2) % MOD;
tmp2--;
ret += tmp1 * comb.comb(num-2, i) % MOD;
}
return ret % MOD;
}
//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];
LL c = culc(range, 1);
for(int i=idx; i<ls[a].size()-1; i++){
dp[a][b][ok] += c*solve(a+1, ls[a][i]+1, 1);
c *= 2;
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:66:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a == v.size()-1) return 1;
~~^~~~~~~~~~~~~
boat.cpp:76: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:106:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
boat.cpp:112: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:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
boat.cpp:94: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 |
22 ms |
8320 KB |
Output is correct |
| 2 |
Correct |
27 ms |
8320 KB |
Output is correct |
| 3 |
Correct |
28 ms |
8440 KB |
Output is correct |
| 4 |
Correct |
22 ms |
8320 KB |
Output is correct |
| 5 |
Correct |
23 ms |
8320 KB |
Output is correct |
| 6 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 7 |
Correct |
20 ms |
8320 KB |
Output is correct |
| 8 |
Correct |
21 ms |
8320 KB |
Output is correct |
| 9 |
Correct |
17 ms |
8320 KB |
Output is correct |
| 10 |
Correct |
19 ms |
8320 KB |
Output is correct |
| 11 |
Correct |
17 ms |
8320 KB |
Output is correct |
| 12 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 13 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 14 |
Correct |
24 ms |
8320 KB |
Output is correct |
| 15 |
Correct |
19 ms |
8320 KB |
Output is correct |
| 16 |
Incorrect |
5 ms |
1792 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
8320 KB |
Output is correct |
| 2 |
Correct |
27 ms |
8320 KB |
Output is correct |
| 3 |
Correct |
28 ms |
8440 KB |
Output is correct |
| 4 |
Correct |
22 ms |
8320 KB |
Output is correct |
| 5 |
Correct |
23 ms |
8320 KB |
Output is correct |
| 6 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 7 |
Correct |
20 ms |
8320 KB |
Output is correct |
| 8 |
Correct |
21 ms |
8320 KB |
Output is correct |
| 9 |
Correct |
17 ms |
8320 KB |
Output is correct |
| 10 |
Correct |
19 ms |
8320 KB |
Output is correct |
| 11 |
Correct |
17 ms |
8320 KB |
Output is correct |
| 12 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 13 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 14 |
Correct |
24 ms |
8320 KB |
Output is correct |
| 15 |
Correct |
19 ms |
8320 KB |
Output is correct |
| 16 |
Incorrect |
5 ms |
1792 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
8320 KB |
Output is correct |
| 2 |
Correct |
27 ms |
8320 KB |
Output is correct |
| 3 |
Correct |
28 ms |
8440 KB |
Output is correct |
| 4 |
Correct |
22 ms |
8320 KB |
Output is correct |
| 5 |
Correct |
23 ms |
8320 KB |
Output is correct |
| 6 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 7 |
Correct |
20 ms |
8320 KB |
Output is correct |
| 8 |
Correct |
21 ms |
8320 KB |
Output is correct |
| 9 |
Correct |
17 ms |
8320 KB |
Output is correct |
| 10 |
Correct |
19 ms |
8320 KB |
Output is correct |
| 11 |
Correct |
17 ms |
8320 KB |
Output is correct |
| 12 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 13 |
Correct |
18 ms |
8320 KB |
Output is correct |
| 14 |
Correct |
24 ms |
8320 KB |
Output is correct |
| 15 |
Correct |
19 ms |
8320 KB |
Output is correct |
| 16 |
Incorrect |
5 ms |
1792 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
