Submission #342029

#TimeUsernameProblemLanguageResultExecution timeMemory
342029thecodingwizardBoat (APIO16_boat)C++11
100 / 100
659 ms6636 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define ii pair<int, int> #define f first #define s second #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() #define F0R(i, n) for (int i = 0; i < n; i++) #define FOR(i, a, b) for (int i = a; i < b; i++) #define inf 1000000010 const int mod = 1e9+7; ll binpow(ll x, ll n, ll m) { assert(n >= 0); x %= m; //note: m*m must be less than 2^63 to avoid ll overflow ll res = 1; while (n > 0) { if (n % 2 == 1) //if n is odd res = res * x % m; x = x * x % m; n /= 2; //divide by two } return res; } int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; ii A[n]; map<int, int> compress; set<int> setValues; setValues.insert(0); setValues.insert(1); F0R(i, n) { cin >> A[i].f >> A[i].s; A[i].s++; setValues.insert(A[i].f); setValues.insert(A[i].s); } int idx = 0; vector<int> values; for (auto x : setValues) { compress[x] = idx; values.pb(x); idx++; } F0R(i, n) { A[i].f = compress[A[i].f]; A[i].s = compress[A[i].s]; } // ct[i][j] = nCr(len + j - 1, j) int ct[values.size()][n+1]; F0R(i, values.size()-1) { F0R(j, n+1) { if (j == 0) ct[i][j] = 0; else { int len = values[i+1]-values[i]; if (j == 1) ct[i][j] = len; else { ct[i][j] = ((ll)ct[i][j-1]*(len+j-1)%mod*binpow(j, mod-2, mod))%mod; } } } ct[i][0] = 0; } int dp[n][values.size()]; int dpSum[n][values.size()]; F0R(i, n) { F0R(j, values.size()-1) { if (j == 0) { dp[i][j] = 1; continue; } dp[i][j] = 0; int num = 0; for (int k = i-1; k >= -1; k--) { if (A[k+1].f <= j && A[k+1].s > j) { num++; dp[i][j] = (dp[i][j] + (ll)(k>=0?dpSum[k][j-1]:1)*ct[j][num])%mod; } } } F0R(j, values.size()-1) { dpSum[i][j] = ((j?dpSum[i][j-1]:0)+dp[i][j])%mod; } } ll ans = 0; FOR(j, 1, values.size()-1) { ans = (ans + dp[n-1][j]) % mod; } cout << ans << endl; return 0; }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:13:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define F0R(i, n) for (int i = 0; i < n; i++)
......
   59 |     F0R(i, values.size()-1) {
      |         ~~~~~~~~~~~~~~~~~~           
boat.cpp:59:5: note: in expansion of macro 'F0R'
   59 |     F0R(i, values.size()-1) {
      |     ^~~
boat.cpp:13:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define F0R(i, n) for (int i = 0; i < n; i++)
......
   76 |         F0R(j, values.size()-1) {
      |             ~~~~~~~~~~~~~~~~~~       
boat.cpp:76:9: note: in expansion of macro 'F0R'
   76 |         F0R(j, values.size()-1) {
      |         ^~~
boat.cpp:13:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define F0R(i, n) for (int i = 0; i < n; i++)
......
   88 |         F0R(j, values.size()-1) {
      |             ~~~~~~~~~~~~~~~~~~       
boat.cpp:88:9: note: in expansion of macro 'F0R'
   88 |         F0R(j, values.size()-1) {
      |         ^~~
boat.cpp:14:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 | #define FOR(i, a, b) for (int i = a; i < b; i++)
......
   94 |     FOR(j, 1, values.size()-1) {
      |         ~~~~~~~~~~~~~~~~~~~~~           
boat.cpp:94:5: note: in expansion of macro 'FOR'
   94 |     FOR(j, 1, values.size()-1) {
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...