| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 47258 |
2018-04-29T18:37:31 Z |
ngkan146 |
Boat (APIO16_boat) |
C++11 |
|
66 ms |
4844 KB |
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = (ll) 1e9+7;
int n, a[505], b[505];
ll f[505][3005];
ll g[505];
int main(){
iostream::sync_with_stdio(0);
cin >> n;
vector <int> lst;
for(int i=1;i<=n;i++)
cin >> a[i] >> b[i],
lst.push_back(a[i]),
lst.push_back(b[i]);
sort(lst.begin(), lst.end());
lst.resize(unique(lst.begin(),lst.end()) - lst.begin());
vector <pair<int,int> > range;
for(int i=0;i<lst.size();i++){
range.push_back({lst[i], lst[i]});
if (i != lst.size() - 1 && lst[i]+1 <= lst[i+1]-1)
range.push_back({lst[i]+1, lst[i+1]-1});
}
range.insert(range.begin(), {-1,-1});
g[0] = 1;
ll ans = 0;
for(int j = 1;j < range.size();j ++){
// f[i][j] = cnt of way that end at i and value of i in range j
int len = range[j].second - range[j].first + 1;
ll arr[505], sumG[505];
arr[0] = 1;
sumG[0] = g[0];
for(int i=1;i<=n;i++)
sumG[i] = (sumG[i-1] + g[i]) % mod,
arr[i] = arr[i-1] * (len+1-i) % mod;
for(int i=1;i<=n;i++){
if (range[j].first < a[i] || b[i] < range[j].second)
continue;
int possiBoat = 0;
ll tmp = 0;
for(int ii=i;ii>=1;ii--){
if (!(a[ii] <= range[j].first && range[j].second <= b[ii])) continue;
possiBoat += (a[ii] <= range[j].first && range[j].second <= b[ii]);
tmp = (tmp + arr[possiBoat]) % mod;
if (possiBoat > len) break;
f[i][j] = (f[i][j] + sumG[ii-1 ] * tmp % mod) % mod;
}
ans = (ans + f[i][j]) % mod;
}
for(int i=0;i<=n;i++){
g[i] = (g[i] + f[i][j]) % mod;
}
}
cout << ans;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<lst.size();i++){
~^~~~~~~~~~~
boat.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i != lst.size() - 1 && lst[i]+1 <= lst[i+1]-1)
~~^~~~~~~~~~~~~~~~~
boat.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 1;j < range.size();j ++){
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2424 KB |
Output is correct |
| 2 |
Correct |
12 ms |
2536 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2536 KB |
Output is correct |
| 4 |
Correct |
12 ms |
2536 KB |
Output is correct |
| 5 |
Correct |
11 ms |
2536 KB |
Output is correct |
| 6 |
Correct |
11 ms |
2564 KB |
Output is correct |
| 7 |
Correct |
10 ms |
2564 KB |
Output is correct |
| 8 |
Correct |
11 ms |
2564 KB |
Output is correct |
| 9 |
Correct |
11 ms |
2624 KB |
Output is correct |
| 10 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 11 |
Correct |
11 ms |
2624 KB |
Output is correct |
| 12 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 13 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 14 |
Correct |
11 ms |
2624 KB |
Output is correct |
| 15 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 16 |
Correct |
5 ms |
2624 KB |
Output is correct |
| 17 |
Correct |
5 ms |
2764 KB |
Output is correct |
| 18 |
Correct |
5 ms |
2772 KB |
Output is correct |
| 19 |
Correct |
5 ms |
2772 KB |
Output is correct |
| 20 |
Correct |
5 ms |
2772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2424 KB |
Output is correct |
| 2 |
Correct |
12 ms |
2536 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2536 KB |
Output is correct |
| 4 |
Correct |
12 ms |
2536 KB |
Output is correct |
| 5 |
Correct |
11 ms |
2536 KB |
Output is correct |
| 6 |
Correct |
11 ms |
2564 KB |
Output is correct |
| 7 |
Correct |
10 ms |
2564 KB |
Output is correct |
| 8 |
Correct |
11 ms |
2564 KB |
Output is correct |
| 9 |
Correct |
11 ms |
2624 KB |
Output is correct |
| 10 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 11 |
Correct |
11 ms |
2624 KB |
Output is correct |
| 12 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 13 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 14 |
Correct |
11 ms |
2624 KB |
Output is correct |
| 15 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 16 |
Correct |
5 ms |
2624 KB |
Output is correct |
| 17 |
Correct |
5 ms |
2764 KB |
Output is correct |
| 18 |
Correct |
5 ms |
2772 KB |
Output is correct |
| 19 |
Correct |
5 ms |
2772 KB |
Output is correct |
| 20 |
Correct |
5 ms |
2772 KB |
Output is correct |
| 21 |
Incorrect |
66 ms |
4844 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
2424 KB |
Output is correct |
| 2 |
Correct |
12 ms |
2536 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2536 KB |
Output is correct |
| 4 |
Correct |
12 ms |
2536 KB |
Output is correct |
| 5 |
Correct |
11 ms |
2536 KB |
Output is correct |
| 6 |
Correct |
11 ms |
2564 KB |
Output is correct |
| 7 |
Correct |
10 ms |
2564 KB |
Output is correct |
| 8 |
Correct |
11 ms |
2564 KB |
Output is correct |
| 9 |
Correct |
11 ms |
2624 KB |
Output is correct |
| 10 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 11 |
Correct |
11 ms |
2624 KB |
Output is correct |
| 12 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 13 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 14 |
Correct |
11 ms |
2624 KB |
Output is correct |
| 15 |
Correct |
10 ms |
2624 KB |
Output is correct |
| 16 |
Correct |
5 ms |
2624 KB |
Output is correct |
| 17 |
Correct |
5 ms |
2764 KB |
Output is correct |
| 18 |
Correct |
5 ms |
2772 KB |
Output is correct |
| 19 |
Correct |
5 ms |
2772 KB |
Output is correct |
| 20 |
Correct |
5 ms |
2772 KB |
Output is correct |
| 21 |
Incorrect |
66 ms |
4844 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
