Submission #218147

#TimeUsernameProblemLanguageResultExecution timeMemory
218147SamAndBoat (APIO16_boat)C++17
9 / 100
902 ms14328 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1003; const int M = 1000000007; int ast(int x, int n) { int ans = 1; while (n) { if (n % 2 == 1) ans = (ans * 1LL * x) % M; x = (x * 1LL * x) % M; n /= 2; } return ans; } int n; int l[N], r[N]; vector<int> v; int c[N][N]; int pc[N][N]; int dp[N][N]; int p[N][N]; int pp[N][N]; int ans; void rec(int i) { if (i == n + 1) { if (!v.empty()) ++ans; return; } rec(i + 1); for (int j = l[i]; j <= r[i]; ++j) { if (v.empty() || v.back() < j) { v.push_back(j); rec(i + 1); v.pop_back(); } } } int main() { //freopen("input.txt", "r", stdin); scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d%d", &l[i], &r[i]); v.push_back(l[i]); v.push_back(r[i] + 1); } sort(v.begin(), v.end()); vector<int> vv; for (int i = 0; i < v.size(); ++i) { if (!i || v[i] != v[i - 1]) vv.push_back(v[i]); } v = vv; for (int i = 0; i < v.size() - 1; ++i) { for (int k = 0; k <= n; ++k) { c[i][k] = 1; int f = 1; for (int j = 1; j <= k; ++j) { c[i][k] = (c[i][k] * 1LL * (v[i + 1] - v[i] - j + 1)) % M; f = (f * 1LL * j) % M; } c[i][k] = (c[i][k] * 1LL * ast(f, M - 2)) % M; if (k > 1) pc[i][k] = (pc[i][k - 1] + c[i][k]) % M; } } for (int i = 1; i <= n; ++i) { for (int j = 0; j < v.size() - 1; ++j) { if (!(l[i] <= v[j] && v[j + 1] - 1 <= r[i])) continue; int q = 0; for (int k = i; k >= 1; --k) { if (!(l[k] <= v[j] && v[j + 1] - 1 <= r[k])) continue; ++q; if (k - 1 == 0 || j - 1 == -1) { if (i == k) dp[i][j] = (dp[i][j] + c[j][q]) % M; else dp[i][j] = (dp[i][j] + pc[j][q]) % M; } else { if (i == k) dp[i][j] = (dp[i][j] + (pp[k - 1][j - 1] + 1) * 1LL * c[j][q]) % M; else dp[i][j] = (dp[i][j] + (pp[k - 1][j - 1] + 1) * 1LL * pc[j][q]) % M; } } } for (int j = 0; j < v.size() - 1; ++j) { p[i][j] = (p[i - 1][j] + dp[i][j]) % M; } pp[i][0] = p[i][0]; for (int j = 1; j < v.size() - 1; ++j) pp[i][j] = (pp[i][j - 1] + p[i][j]) % M; } printf("%d\n", pp[n][v.size() - 2]); //v.clear(); //rec(1); //printf("%d\n", ans); return 0; }

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
boat.cpp:69:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size() - 1; ++i)
                     ~~^~~~~~~~~~~~~~
boat.cpp:87:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size() - 1; ++j)
                         ~~^~~~~~~~~~~~~~
boat.cpp:113:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size() - 1; ++j)
                         ~~^~~~~~~~~~~~~~
boat.cpp:118:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < v.size() - 1; ++j)
                         ~~^~~~~~~~~~~~~~
boat.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &l[i], &r[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...