| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 282531 |
2020-08-24T14:15:54 Z |
AaronNaidu |
Boat (APIO16_boat) |
C++14 |
|
5 ms |
2432 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007;
int n;
ll x;
vector<ll> v;
vector<pair<ll, int> > ycoords;
int indexes[501];
ll dp[501][501];
ll getDP(int a, int b) {
if (a == -1)
{
return 1;
}
if (dp[a][b] > 0)
{
return dp[a][b];
}
ll ans = 0;
if (ycoords[b].first >= v[a])
{
ans += getDP(a-1, indexes[a]);
ans %= mod;
}
ans += getDP(a-1, b);
ans %= mod;
dp[a][b] = ans;
return ans;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x >> x;
v.push_back(x);
ycoords.push_back({x, i});
}
sort(ycoords.begin(), ycoords.end());
for (int i = 0; i < n; i++)
{
indexes[ycoords[i].second] = i;
}
ll ans = getDP(n-1, n-1) - 1;
if (ans < 0)
{
ans += mod;
}
ans %= mod;
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2432 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2304 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2304 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2280 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2304 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 16 |
Incorrect |
5 ms |
2304 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2432 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2304 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2304 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2280 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2304 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 16 |
Incorrect |
5 ms |
2304 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2432 KB |
Output is correct |
| 2 |
Correct |
5 ms |
2304 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 7 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 8 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 9 |
Correct |
5 ms |
2304 KB |
Output is correct |
| 10 |
Correct |
4 ms |
2280 KB |
Output is correct |
| 11 |
Correct |
5 ms |
2304 KB |
Output is correct |
| 12 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 13 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 14 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 15 |
Correct |
4 ms |
2304 KB |
Output is correct |
| 16 |
Incorrect |
5 ms |
2304 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
