| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1107169 |
2024-10-31T18:21:56 Z |
ASN49K |
Boat (APIO16_boat) |
C++14 |
|
12 ms |
8528 KB |
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define int i64
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7,inf=1e9+1;
const i64 INF=1e18;
mt19937 rng(69);
int prod(int x,int y)
{
return (1LL*x*y)%mod;
}
int add(int x,int y)
{
assert(y>=0 && y<mod && x<mod);
return (x+y)%mod;
}
int pw2(int a,int p)
{
int rez=1;
while(p>0)
{
if(p&1)
{
rez=prod(rez,a);
}
p>>=1;
a=prod(a,a);
}
return rez;
}
const int N=500;
int dp[2*N+1][N+1],sum[2*N+1];
int fact[N+1],inv[N+1];
void pre_proc()
{
fact[0]=1,inv[0]=1;
for(int i=1;i<=N;i++)
{
fact[i]=prod(fact[i-1] , i);
inv[i]=pw2(fact[i] , mod-2);
}
}
int comb(int k,int n)
{
if(k>n)
{
return 0;
}
int rez=1;
for(int i=0;i<k;i++)
{
rez=prod(rez , n-i);
}
return prod(rez,inv[k]);
}
main()
{
pre_proc();
int n;
cin>>n;
//segmente de forma [x,y)
vector<pair<int,int>>a(n);
vector<int>poz(1,0);
poz.reserve(2*n+1);
for(auto &c:a)
{
cin>>c.first>>c.second;
c.second++;
poz.pb(c.first);
poz.pb(c.second);
}
sort(all(poz));
poz.erase(unique(all(poz)) , poz.end());
for(int i=0;i<poz.size()-1;i++)
{
sum[i]=1;
}
dp[0][1]=1;
vector<vector<int>>combb(poz.size()-1 , vector<int>(n+1));
for(int i=1;i<poz.size()-1;i++)
{
int aux=1;
for(int j=1;j<=n;j++)
{
aux=prod(aux , poz[i+1]-poz[i]-j+1);
combb[i][j]=prod(aux , inv[j]);
}
}
for(auto &c:a)
{
c.first=lower_bound(all(poz) , c.first)-poz.begin();
c.second=lower_bound(all(poz) , c.second)-poz.begin()-1;
for(int i=c.first;i<=c.second;i++)
{
for(int j=n;j>=2;j--)
{
dp[i][j]=add(dp[i][j] , dp[i][j-1]);
}
dp[i][1]=add(dp[i][1] , sum[i-1]);
}
for(int i=1;i<poz.size()-1;i++)
{
sum[i]=sum[i-1];
for(int j=1;j<=n;j++)
{
//if(c.first==2)cout<< prod(dp[i][j] , comb(j,poz[i+1]-poz[i]))<<' ';
sum[i]=add(sum[i] , prod(dp[i][j] , combb[poz[i+1]-poz[i]][j]));
}
//cout<<'\n';
//cout<<sum[i]<<' ';
}
//cout<<'\n';
}
cout<<sum[poz.size()-2]-1;
}
Compilation message
boat.cpp:59:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
59 | main()
| ^~~~
boat.cpp: In function 'int main()':
boat.cpp:78:18: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=0;i<poz.size()-1;i++)
| ~^~~~~~~~~~~~~
boat.cpp:86:18: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i=1;i<poz.size()-1;i++)
| ~^~~~~~~~~~~~~
boat.cpp:107:22: warning: comparison of integer expressions of different signedness: 'i64' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int i=1;i<poz.size()-1;i++)
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
8528 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
8528 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
2024 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
8528 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
