| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 262796 |
2020-08-13T09:11:38 Z |
hohohaha |
Boat (APIO16_boat) |
C++14 |
|
399 ms |
18168 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int, int>
#define vii vector<ii>
#define iii pair<int, ii>
#define viii vector<iii>
#define ld long double
#define li long long
#define eb emplace_back
#define vi vector<int>
#define fi first
#define se second
const int mod = 1e9+7, maxn = 505;
int n, l[maxn], r[maxn], low[maxn][maxn], up[maxn][maxn], C[maxn][2*maxn], back[2*maxn][maxn], fac[maxn], dp[maxn][2*maxn][2], sdp[maxn][maxn];
vi all;
vii seg;
void add(int& a, int b)
{
a = (a+b)%mod;
}
int mul(int a, int b)
{
return a*b%mod;
}
int binpow(int x, int k)
{
if(!k) return 1;
int t = binpow(x, k/2);
if(k&1) return mul(mul(t, t), x);
return mul(t, t);
}
int inv(int x)
{
return binpow(x, mod-2);
}
void init()
{
for(int i=0; i<=n; i++)
{
if(!i) fac[i] = 1;
else fac[i] = mul(fac[i-1], i);
}
}
signed main()
{
cin>>n;
init();
for(int i=1; i<=n; i++)
{
cin>>l[i]>>r[i];
all.eb(l[i]);
all.eb(r[i]);
}
all.eb(0);
for(int i=1; i<=n; i++)
{
low[i][i] = l[i];
up[i][i] = r[i];
for(int j=i+1; j<=n; j++)
{
low[i][j] = max(low[i][j-1], l[j]);
up[i][j] = min(up[i][j-1], r[j]);
}
}
sort(begin(all), end(all));
seg.eb(0, 0);
for(int i=1; i<all.size(); i++)
{
if(all[i]-all[i-1]) seg.eb(all[i-1]+1, all[i]);
}
for(int i=1; i<seg.size(); i++)
{
// cout<<i<<" "<<endl;
int range = seg[i].fi - seg[i].se+1;
for(int j=0; j<=n; j++)
{
// cout<<j<<endl;
if(!j) back[i][j]=1;
else back[i][j] = mul(back[i][j-1], range - j+1);
C[j][i] = mul(back[i][j], inv(fac[j]));
}
}
dp[0][0][0] = 1;
for(int i=0; i<=n; i++)
{
for(int k=0; k<seg.size(); k++)
{
if(i)
{
if(!k)
{
dp[i][k][0] = 1;
dp[i][k][1] = 0;
}
else
{
for(int j=1; j<=i; j++)
{
add(dp[i][k][0], dp[j-1][k][1]);
if(low[j][i]<=seg[k].fi and seg[k].se<=up[j][i])
add(dp[i][k][1], mul(sdp[j-1][k-1], C[i-j+1][k]));
}
}
// cout<<i<<" "<<k<<": 0: "<<dp[i][k][0]<<" 1: "<<dp[i][k][1]<<endl;
}
add(sdp[i][k], dp[i][k][0]);
add(sdp[i][k], dp[i][k][1]);
if(k) add(sdp[i][k], sdp[i][k-1]);
}
}
int ans = sdp[n][seg.size()-1]-1;
while(ans<0) add(ans, mod);
cout<<ans;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:77:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=1; i<all.size(); i++)
| ~^~~~~~~~~~~
boat.cpp:81:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(int i=1; i<seg.size(); i++)
| ~^~~~~~~~~~~
boat.cpp:96:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int k=0; k<seg.size(); k++)
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
399 ms |
18168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
399 ms |
18168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
3584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
399 ms |
18168 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
