| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 970750 |
2024-04-27T08:06:28 Z |
starchan |
Boat (APIO16_boat) |
C++17 |
|
2000 ms |
53328 KB |
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in array<int, 2>
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
const int mod = 1e9+7;
const int MX = 5e3+5;
int inv[MX];
int dp[MX][2*MX];
int ans[2*MX];
int R[MX][2*MX];
int C[MX][2*MX];
void pre()
{
inv[1] = 1;
for(int i = 2; i < MX; i++)
{
inv[i] = (-(mod/i)*inv[mod%i])%mod; inv[i]+=mod;
inv[i]%=mod;
}
}
int solve(int a, int b, int c, int d)
{
int cnt = b+d-a-c;
for(int i = a; i < b; i++)
{
for(int j = c; j < d; j++)
{
if(i < j)
cnt++;
}
}
return cnt;
}
signed main()
{
fast();
pre();
vector<int> v;
int n;
cin >> n;
n++;
vector<in> a(n+1);
for(int i = 1; i < n; i++)
{
cin >> a[i][0] >> a[i][1];
v.pb(a[i][0]); v.pb(++a[i][1]);
}
cout << "EXPECTED ANS = " << solve(a[1][0], a[1][1], a[2][0], a[2][1]) << endl;
a[n][0] = 1e9+1; a[n][1] = 1e9+2;
v.pb(a[n][0]); v.pb(a[n][1]);
sort(v.begin(), v.end());
vector<int> CC; CC.pb(v[0]);
for(auto x: v)
{
if(x != CC.back())
CC.pb(x);
}
int M = CC.size();
for(int i = 0; i < M-1; i++)
{
C[0][i] = 1; int tm = CC[i+1]-CC[i];
for(int j = 1; j <= n; j++)
{
if(j > tm)
break;
C[j][i] = C[j-1][i]*(tm-j+1); C[j][i]%=mod;
C[j][i]*=inv[j]; C[j][i]%=mod;
}
//for(int j = 0; j <= n; j++)
// cout << C[j][i] << " ";
//cout << "\n";
}
for(int i = 1; i <= n; i++)
{
a[i][0] = lower_bound(CC.begin(), CC.end(), a[i][0])-CC.begin();
a[i][1] = lower_bound(CC.begin(), CC.end(), a[i][1])-CC.begin();
}
for(int i = 0; i < M; i++)
R[0][i] = ans[i] = 1;
//cout << endl;
for(int i = 1; i <= n; i++)
{
//cout << "Currently processing i = " << i << endl;
for(int j = a[i][0]; j < a[i][1]; j++)
{
//R[L][j] = number of ways to do stuff if picking L things from jth bracket.
//cout << "Bracket range = [" << CC[j] << ", " << CC[j+1] << ")" << endl;
for(int L = 0; L < i; L++)
{
//cout << "If we pick L = " << L << " things in the current (" << j << ") bracket, we have: " << endl;
//cout << R[L][j] << endl;
dp[i][j]+=((R[L][j]*C[L+1][j])%mod);
}
dp[i][j]%=mod;
for(int T = j; T < M-1; T++)
{
ans[T]+=dp[i][j];
ans[T]%=mod;
}
//cout << "For j, computed: " << dp[i][j] << endl;
//Currently working in intervl [CC[j], CC[j+1])
}
for(int j = a[i][0]; j < a[i][1]; j++)
{
//how does R[L][j] change?
for(int L = i; L >= 1; L--)
{
R[L][j]+=R[L-1][j];
R[L][j]%=mod;
}
}
for(int j = 1; j < M-1; j++)
R[0][j] = ans[j-1];
}
dp[n][M-2]+=(mod-1); dp[n][M-2]%=mod;
cout << dp[n][M-2] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
53328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
53328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2052 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
53328 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
