| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 242879 |
2020-06-29T15:59:02 Z |
Redhood |
Boat (APIO16_boat) |
C++14 |
|
975 ms |
7288 KB |
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define mkp make_pair
#define pb push_back
#define len(x) (int)(x).size()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int MOD = (int)1e9 + 7, N = 500 , NN = 1001;
int pw(int a , int b){
if(b == 0)return 1;
int ans = pw(a , b >> 1);
ans = (1ll * ans * ans) % MOD;
if(b & 1)
ans = (1ll * ans * a) % MOD;
return ans;
}
int f[4*N][N] , inv[N] , fact[N];
int C[N][N] , done[4*N][N] , cnt[4*N][N];
void md(int &a){
if(a >= MOD)a-=MOD;
}
void COMBA(vector<pii>&lines){
fact[0] = 1;
for(int i = 1 ; i < N; ++i)
fact[i] = (1ll * fact[i-1] * i) % MOD;
inv[N-1] = pw(fact[N-1], MOD-2);
for(int i = N-2;i>=0;--i)
inv[i] = (1ll * inv[i+1]*(i+1))%MOD;
for(int i = 0 ; i < N; ++i){
C[i][0] = 1;
for(int j = 1; j <= i ; ++j){
C[i][j] = C[i-1][j] + C[i-1][j-1];
md(C[i][j]);
}
}
/// fucking cnt[i][j]
for(int i = 1; i < len(lines); ++i){
for(int want = 0 ;want < N; ++want){
int len = lines[i].se - lines[i].fi + 1;
if(len < want)
done[i][want] = 0;
else{
ll answer = 1;
for(int j = len-want + 1; j<= len; ++j){
answer = (1ll * answer * j) % MOD;
}
answer = (1ll * answer * inv[want]) % MOD;
done[i][want] = answer;
}
}
}
for(int i = 0 ; i < len(lines); ++i){
for(int j = 1 ; j < N; ++j){
for(int k = 0 ; k < j; ++k){
cnt[i][j] += (1ll * C[j-1][k] * done[i][j-k])%MOD;
md(cnt[i][j]);
}
}
}
}
signed main(){
ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
int n;cin >> n;
vector<pii>boats(n);
for(auto&i:boats)cin>>i.fi>>i.se;
/// lulz wtf is going on here
set < int > dots;
for(auto x : boats)
dots.insert(x.fi) , dots.insert(x.se);
vector<pii>lines;
lines.pb({0 , 0});
for(auto i : dots)
lines.pb(mkp(i , i));
auto it = dots.begin();
int prev = *it;
++it;
while(it != dots.end()){
if(prev + 1 <= *it-1)
lines.pb({prev + 1 , *it-1});
prev = *it;
++it;
}
for(auto &i : boats){
int l = lower_bound(all(lines) , mkp(i.fi , -1))-lines.begin();
int r = lower_bound(all(lines) , mkp(i.se + 1 , -1))-lines.begin() - 1;
i = mkp(l , r);
}
COMBA(lines);
for(int i = 0 ; i < n; ++i)
f[0][i] = 1;
for(int i = 1; i < len(lines); ++i){
for(int j = 0; j < N; ++j)
f[i][j] = f[i-1][j];
/// what if we skip anybody
for(int j = 1; j <= n; ++j){
int cur = j;
int bad = 0;
for(int k = 1; k <= n , cur>0; ++k , --cur){
if(boats[cur-1].se < i || boats[cur-1].fi > i)
{bad++;continue;}
/// firstly update answer
f[i][j] += (f[i-1][j-k]*1ll*cnt[i][k - bad])%MOD;
md(f[i][j]);
}
}
// cout << " I " << i << '\n';
// for(int j = 0 ; j <= n; ++j)
// cout << f[i][j] << ' ' ;
// cout << '\n';
}
cout << f[len(lines)-1][n];
return 0;
}
Compilation message
boat.cpp: In function 'int main()':
boat.cpp:114:30: warning: left operand of comma operator has no effect [-Wunused-value]
for(int k = 1; k <= n , cur>0; ++k , --cur){
~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
975 ms |
7288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
975 ms |
7288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
342 ms |
3832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
975 ms |
7288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
