Submission #49595

#TimeUsernameProblemLanguageResultExecution timeMemory
49595wzyBoat (APIO16_boat)C++11
0 / 100
2146 ms524288 KiB
#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[700][700]; vector<int> s; vector<pii> lines; vector<pii> segments; int n ; int dp[200][400][200][3]; bool vis[200][400][200][3]; int custo(int i , int k){ int U = segments[i].S - segments[i].F+1; if(k > U) return 0; return C[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 < 400 ; 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 for(int i = 0 ; i < 700 ; i++){ C[i][0] = 1 , C[i][1] = i; } for(int i = 1 ; i < 700 ; i++){ for(int j = 2 ; j < i ; j++){ C[i][j] = C[i-1][j-1] + C[i-1][j]; } } // 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 < s.size() - 1 ; i++){ segments.pb(pii(s[i] , s[i+1])); } printf("%lld\n" , solve(0,0,0,1) - segments.size()); }

Compilation message (stderr)

boat.cpp: In function 'long long int solve(long long int, long long int, long long int, long long int)':
boat.cpp:26:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(j == segments.size()){
     ~~^~~~~~~~~~~~~~~~~~
boat.cpp: In function 'int32_t main()':
boat.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < s.size() - 1 ; i++){
                  ~~^~~~~~~~~~~~~~
boat.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &n);
  ~~~~~^~~~~~~~~~~~~
boat.cpp:78: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...