| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49597 |
2018-05-31T23:59:07 Z |
wzy |
Boat (APIO16_boat) |
C++11 |
|
2000 ms |
524288 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
int mod = 1000000007;
int C[600][600];
vector<int> s;
vector<pii> lines;
vector<pii> segments;
int n ;
int dp[200][300][200][3];
bool vis[200][300][200][3];
map<pii, int> custop;
int bexp(int x , int y){
if(y == 0) return 1;
if(y == 1) return x;
int pp = bexp(x, y/2);
pp *= pp;
pp%=mod;
if(y%2) pp*=x;
pp%=mod;
return pp;
}
int custo(int i , int k){
int U = segments[i].S - segments[i].F+1;
if(k > U) return 0;
return custop[pii(U,k)];
}
int solve(int i , int j , int k, int w){
if(j == segments.size()){
if(w == 0){
return 0;
}
else return 1;
}
if(i == n){
if(w == 0){
if(k == 0) return 0;
else return custo(j,k);
}
return w;
}
if(vis[i][j][k][w]) return dp[i][j][k][w];
vis[i][j][k][w] = 1;
if(w){
dp[i][j][k][w] = (solve(i, j + 1 , 0 , 1) + solve(i , j , 0 , 0))%mod;
}
else{
dp[i][j][k][w] = solve(i+1,j,k,w);
dp[i][j][j][w] %= mod;
if(k > 0){
dp[i][j][k][w] += solve(i+1,j+1,0,1)*custo(j,k);
dp[i][j][k][w] %= mod;
}
if(lines[i].F <= segments[j].F && lines[i].S >= segments[j].S){
dp[i][j][k][w] += solve(i+1,j,k+1,0);
dp[i][j][k][w] %= mod;
}
}
return dp[i][j][k][w];
}
int32_t main(){
scanf("%lld" , &n);
for(int i = 0 ; i < 200 ; i++)
for(int j = 0 ; j < 300 ; j++)
for(int k = 0 ; k < 200 ; k++)
for(int w = 0 ;w < 3 ; w++) dp[i][j][k][w] = 0 , vis[i][j][k][w] = 0;
// fill C
//
lines.resize(n);
for(int i = 0 ; i < n; i++){
scanf("%lld%lld", &lines[i].F , &lines[i].S);
s.pb(lines[i].F) , s.pb(lines[i].S);
}
sort(lines.begin() , lines.end());
for(int i = 0 ; i < ((int)s.size()) - 1 ; i++){
segments.pb(pii(s[i] , s[i+1]));
}
for(int i = 0 ; i < segments.size() ; i++){
int U = segments[i].S - segments[i].F + 1;
for(int j = 0 ; j <= min(U, n) ; j++){
if(j == 0) custop[pii(U, j)] = 1;
if(j == 1) custop[pii(U, j)] = U;
else{
custop[pii(U,j)] = custop[pii(U, j-1)]%mod;
custop[pii(U,j)] *= (U - j + 1);
custop[pii(U,j)] %= mod;
custop[pii(U,j)] *= bexp(j , mod-2);
custop[pii(U,j)] %= mod;
}
}
}
printf("%lld\n" , solve(0,0,0,1) - segments.size());
}
Compilation message
boat.cpp: In function 'long long int solve(long long int, long long int, long long int, long long int)':
boat.cpp:37:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(j == segments.size()){
~~^~~~~~~~~~~~~~~~~~
boat.cpp: In function 'int32_t main()':
boat.cpp:89:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0 ; i < segments.size() ; i++){
~~^~~~~~~~~~~~~~~~~
boat.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld" , &n);
~~~~~^~~~~~~~~~~~~
boat.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &lines[i].F , &lines[i].S);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2119 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2119 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
325 ms |
524288 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2119 ms |
524288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
