| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 96114 |
2019-02-06T03:52:26 Z |
oolimry |
Boat (APIO16_boat) |
C++14 |
|
2000 ms |
8312 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, long long> ii;
long long mod = 1000000007;
//long long dp[505][2005];
//static long long dp[505][2005][505];
#define int long long
long long modInverse(long long a, long long m)
{
long long m0 = m;
long long y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1)
{
// q is quotient
long long q = a / m;
long long t = m;
// m is remainder now, process same as
// Euclid's algo
m = a % m, a = t;
t = y;
// Update y and x
y = x - q * y;
x = t;
}
// Make x positive
if (x < 0)
x += m0;
return x;
}
main()
{
//freopen("i.txt","r",stdin);
ios_base::sync_with_stdio(false);
long long inverse[505];
for(long long i = 1;i < 505;i++){
inverse[i] = modInverse(i,mod);
}
int n;
cin >> n;
long long a[n];
long long b[n];
set<long long> s;
for(int i = 0;i < n;i++){
cin >> a[i] >> b[i];
s.insert(a[i]);
s.insert(b[i]);
}
//cout << s.size() << endl;
vector<long long> key;
for(set<long long>::iterator it = s.begin();it != s.end();it++){
key.push_back(*it);
}
//cout << k.size() << endl;
vector<ii> ranges;
for(int i = 0;i < key.size();i++){
ranges.push_back(ii(key[i],key[i]));
if(i != 0){
if(key[i] != key[i-1]+1){
ranges.push_back(ii(key[i-1]+1,key[i]-1));
}
}
}
sort(ranges.begin(),ranges.end());
int m = ranges.size();
//cout << m << "\n";
long long diff[m];
for(int i = 0;i < m;i++){
diff[i] = ranges[i].second - ranges[i].first + 1;
diff[i] %= mod;
//cout << ranges[i].first << " " << ranges[i].second << "\n";
}
static long long dp[2][2005][505];
//boat no, range, number taken b4;
for(int i = 0;i < 2;i++){
for(int j = 0;j < m;j++){
for(int k = 0;k < 505;k++){
dp[i][j][k] = 0ll;
}
}
}
for(int j = 0;j < m;j++){
if(a[0] <= ranges[j].first && b[0] >= ranges[j].second){
dp[0][j][1] = diff[j];
//cout << a[0] << " " << ranges[j].first << " " << ranges[j].second << " " << b[0] << endl;
}
}
for(int i = 1;i < n;i++){
///take nothing for this school
int ii = i % 2;
for(int j = 0;j < m;j++){
for(int k = 1;k < 505;k++){
dp[ii][j][k] = dp[ii^1][j][k];
dp[ii][j][k] %= mod;
}
}
///take same as previous school
for(int j = 0;j < m;j++){
if(a[i] <= ranges[j].first && b[i] >= ranges[j].second){
for(int k = 2;k < 505;k++){
long long x = dp[ii^1][j][k-1];
if(diff[j] - k + 1 <= 0) break;
x *= (diff[j] - k + 1);
x %= mod;
x *= inverse[k];
x %= mod;
dp[ii][j][k] += x;
//dp[ii][j][k] %= mod;
}
}
}
///take for the first time
long long acc = 0ll;
for(int j = 0;j < m;j++){
if(j != 0){
for(int k = 1;k < 505;k++){
acc += dp[ii^1][j-1][k];
acc %= mod;
}
}
if(a[i] <= ranges[j].first && b[i] >= ranges[j].second){
long long x = acc;
x += 1;
x *= diff[j];
acc %= mod;
dp[ii][j][1] += x;
dp[ii][j][1] %= mod;
}
}
}
/*
for(int j = 0;j < m;j++){
cout << ranges[j].first << " " << ranges[j].second << ": ";
for(int i = 0;i < n;i++){
cout << dp[i][j] << " ";
}
cout << "\n";
}
*/
long long ans = 0ll;
for(int j = 0;j < m;j++){
for(int k = 1;k < 505;k++){
ans += dp[(n-1)%2][j][k];
ans %= mod;
if(dp[(n-1)%2][j][k] != 0){
//cout << j << " " << k << " " << dp[(n-1)%2][j][k] << "\n";
}
}
}
cout << ans;
return 0;
}
Compilation message
boat.cpp:39:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main()
^
boat.cpp: In function 'int main()':
boat.cpp:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i < key.size();i++){
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2074 ms |
8312 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2074 ms |
8312 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
576 ms |
3576 KB |
Output is correct |
| 2 |
Correct |
563 ms |
3576 KB |
Output is correct |
| 3 |
Correct |
581 ms |
3576 KB |
Output is correct |
| 4 |
Correct |
600 ms |
3576 KB |
Output is correct |
| 5 |
Correct |
586 ms |
3448 KB |
Output is correct |
| 6 |
Correct |
621 ms |
3704 KB |
Output is correct |
| 7 |
Correct |
633 ms |
3576 KB |
Output is correct |
| 8 |
Correct |
618 ms |
3576 KB |
Output is correct |
| 9 |
Correct |
621 ms |
3576 KB |
Output is correct |
| 10 |
Correct |
618 ms |
3676 KB |
Output is correct |
| 11 |
Correct |
589 ms |
3704 KB |
Output is correct |
| 12 |
Correct |
565 ms |
3448 KB |
Output is correct |
| 13 |
Correct |
573 ms |
3576 KB |
Output is correct |
| 14 |
Correct |
589 ms |
3576 KB |
Output is correct |
| 15 |
Correct |
592 ms |
3576 KB |
Output is correct |
| 16 |
Correct |
250 ms |
1784 KB |
Output is correct |
| 17 |
Correct |
248 ms |
1784 KB |
Output is correct |
| 18 |
Correct |
266 ms |
1784 KB |
Output is correct |
| 19 |
Correct |
252 ms |
1784 KB |
Output is correct |
| 20 |
Correct |
268 ms |
1784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2074 ms |
8312 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
