| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 340167 |
2020-12-27T05:41:33 Z |
blue |
Boat (APIO16_boat) |
C++11 |
|
4 ms |
364 KB |
#include <iostream>
#include <algorithm>
using namespace std;
/*
dp[i][j] = number of valid configurations for schools 1..i but such that i has range a[j] to b[i]
Let us malong longain a long range partitioned by polong longs P[i]
Each section of the range looks like:
A[p] to A[q]-1;
A[p] to B[q]
B[p]+1 to A[q]-1;
B[p]+1 to B[q]
*/
long long mod = 1e9 + 7;
long long a[501], b[501];
long long pos(long long i) //upper acceptable limit of range
{
if(i > 0) return a[i] - 1;
else return b[-i];
}
int main()
{
long long N;
cin >> N;
for(long long i = 1; i <= N; i++) cin >> a[i] >> b[i];
long long I[2*N];
for(long long i = 0; i < N; i++)
{
I[i] = i+1;
I[i+N] = -i-1;
}
sort(I, I+2*N, [] (long long x, long long y)
{
return pos(x) < pos(y);
});
long long dp[2*N]; //number of streams in between I[i-1] and I[i].
for(long long i = 0; i < 2*N; i++) dp[i] = 0;
long long temp = 0;
long long temp2;
for(long long i = 1; i <= N; i++)
{
// cout << "i = " << i << '\n';
temp = 0;
for(long long j = 1; j < 2*N; j++)
{
if(pos(I[j]) <= pos(i)) temp = (temp + dp[j]) % mod;
else if(pos(I[j]) <= pos(-i))
{
temp2 = temp;
temp = (temp + (pos(I[j]) - pos(I[j-1]))*dp[j]) % mod;
if(j > 0) dp[j] = (dp[j] + (pos(I[j]) - pos(I[j-1]))*(temp2 + 1)) % mod;
}
}
// for(long long j = 0; j < 2*N; j++)
// {
// cout << j << ' ' << I[j] << ' ' << pos(I[j]) << ' ' << dp[j] << '\n';
// }
// cout << "_________________________\n";
}
long long res = 0;
for(long long j = 0; j < 2*N; j++) res = (res + dp[j]) % mod;
cout << res << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| 4 |
Correct |
3 ms |
364 KB |
Output is correct |
| 5 |
Correct |
3 ms |
364 KB |
Output is correct |
| 6 |
Correct |
3 ms |
364 KB |
Output is correct |
| 7 |
Correct |
3 ms |
364 KB |
Output is correct |
| 8 |
Correct |
3 ms |
364 KB |
Output is correct |
| 9 |
Correct |
3 ms |
364 KB |
Output is correct |
| 10 |
Correct |
3 ms |
364 KB |
Output is correct |
| 11 |
Correct |
3 ms |
364 KB |
Output is correct |
| 12 |
Correct |
3 ms |
364 KB |
Output is correct |
| 13 |
Correct |
3 ms |
364 KB |
Output is correct |
| 14 |
Correct |
3 ms |
364 KB |
Output is correct |
| 15 |
Correct |
3 ms |
364 KB |
Output is correct |
| 16 |
Correct |
3 ms |
364 KB |
Output is correct |
| 17 |
Correct |
3 ms |
364 KB |
Output is correct |
| 18 |
Correct |
3 ms |
364 KB |
Output is correct |
| 19 |
Correct |
3 ms |
364 KB |
Output is correct |
| 20 |
Correct |
3 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| 4 |
Correct |
3 ms |
364 KB |
Output is correct |
| 5 |
Correct |
3 ms |
364 KB |
Output is correct |
| 6 |
Correct |
3 ms |
364 KB |
Output is correct |
| 7 |
Correct |
3 ms |
364 KB |
Output is correct |
| 8 |
Correct |
3 ms |
364 KB |
Output is correct |
| 9 |
Correct |
3 ms |
364 KB |
Output is correct |
| 10 |
Correct |
3 ms |
364 KB |
Output is correct |
| 11 |
Correct |
3 ms |
364 KB |
Output is correct |
| 12 |
Correct |
3 ms |
364 KB |
Output is correct |
| 13 |
Correct |
3 ms |
364 KB |
Output is correct |
| 14 |
Correct |
3 ms |
364 KB |
Output is correct |
| 15 |
Correct |
3 ms |
364 KB |
Output is correct |
| 16 |
Correct |
3 ms |
364 KB |
Output is correct |
| 17 |
Correct |
3 ms |
364 KB |
Output is correct |
| 18 |
Correct |
3 ms |
364 KB |
Output is correct |
| 19 |
Correct |
3 ms |
364 KB |
Output is correct |
| 20 |
Correct |
3 ms |
364 KB |
Output is correct |
| 21 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
364 KB |
Output is correct |
| 2 |
Correct |
3 ms |
364 KB |
Output is correct |
| 3 |
Correct |
3 ms |
364 KB |
Output is correct |
| 4 |
Correct |
3 ms |
364 KB |
Output is correct |
| 5 |
Correct |
3 ms |
364 KB |
Output is correct |
| 6 |
Correct |
3 ms |
364 KB |
Output is correct |
| 7 |
Correct |
3 ms |
364 KB |
Output is correct |
| 8 |
Correct |
3 ms |
364 KB |
Output is correct |
| 9 |
Correct |
3 ms |
364 KB |
Output is correct |
| 10 |
Correct |
3 ms |
364 KB |
Output is correct |
| 11 |
Correct |
3 ms |
364 KB |
Output is correct |
| 12 |
Correct |
3 ms |
364 KB |
Output is correct |
| 13 |
Correct |
3 ms |
364 KB |
Output is correct |
| 14 |
Correct |
3 ms |
364 KB |
Output is correct |
| 15 |
Correct |
3 ms |
364 KB |
Output is correct |
| 16 |
Correct |
3 ms |
364 KB |
Output is correct |
| 17 |
Correct |
3 ms |
364 KB |
Output is correct |
| 18 |
Correct |
3 ms |
364 KB |
Output is correct |
| 19 |
Correct |
3 ms |
364 KB |
Output is correct |
| 20 |
Correct |
3 ms |
364 KB |
Output is correct |
| 21 |
Incorrect |
4 ms |
364 KB |
Output isn't correct |
| 22 |
Halted |
0 ms |
0 KB |
- |
