제출 #245322

#제출 시각아이디문제언어결과실행 시간메모리
245322neihcr7jBoat (APIO16_boat)C++14
9 / 100
626 ms5112 KiB
#include<bits/stdc++.h> #define M 1000000007 #define maxn 502 using namespace std; typedef long long ll; inline ll norm(ll a) { return (a < 0 ? a + M : (a >= M ? a - M : a)); } inline ll mul(ll a, ll b) { return a * b % M; } ll power(ll a, ll b) { if (b == 0) return 1; if (b&1) return mul(power(a, b - 1), a); ll t = power(a, b / 2); return mul(t, t); } ll gt[maxn * 2], igt[maxn * 2]; void precalc(){ int n = 1000; gt[0] = 1; for (int i = 1; i <= n; ++i) gt[i] = mul(gt[i - 1], i); igt[n] = power(gt[n], M - 2); for (int i = n - 1; i >= 0; --i) igt[i] = mul(igt[i + 1], i + 1); } ll C(int n, int k) { return mul(mul(gt[n], igt[k]), igt[n - k]); } int n; int l[maxn], r[maxn]; vector < pair < int, int > > seg; vector < vector < int > > a; vector < int > leng; ll dp[maxn * 4][maxn]; int main(){ #define TASK "ABC" // freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); ios_base::sync_with_stdio(0); precalc(); cin >> n; vector < int > ret; for (int i = 1; i <= n; ++i) { cin >> l[i] >> r[i]; ret.push_back(l[i]); ret.push_back(r[i]); } sort(ret.begin(), ret.end()); seg.push_back({ret[0], ret[0]}); for (int i = 1; i < ret.size(); ++i) if (ret[i] != ret[i - 1]) { if (i == ret.size() || ret[i] != ret[i + 1]) { seg.push_back({ret[i - 1] + 1, ret[i]}); continue; } if (ret[i - 1] + 1 != ret[i]) seg.push_back({ret[i - 1] + 1, ret[i] - 1}); seg.push_back({ret[i], ret[i]}); } a = vector < vector < int > >(seg.size(), vector < int >(0, 0)); leng = vector < int > (seg.size(), 0); for (int i = 0; i < seg.size(); ++i) { for (int j = 1; j <= n; ++j) if (l[j] <= seg[i].first && seg[i].second <= r[j]) a[i].push_back(j); leng[i] = seg[i].second - seg[i].first + 1; } ll ans = 0; for (int i = 0; i < seg.size(); ++i) { ll l = leng[i]; vector < ll > c(a[i].size() + 1, 0), val(a[i].size() + 1, 0); c[0] = 1; for (int k = 1; k <= a[i].size(); ++k) { if (k <= l) c[k] = mul(mul(c[k - 1], l - k + 1), power(k, M - 2)); for (int x = k; x > 0; --x) if (x <= l) val[k] = norm(val[k] + mul(c[x], C(k - 1, x - 1))); } int index = 0; for (int k = 0; k <= n; ++k) { ll res = (k == 0 ? 1 : 0); for (int j = 0; j < i; ++j) res = norm(res + dp[j][k]); while (index < a[i].size() && a[i][index] <= k) index++; for (int j = index; j < a[i].size(); ++j) dp[i][a[i][j]] = norm(dp[i][a[i][j]] + mul(res, val[j - index + 1])); ans = norm(ans + dp[i][k]); } } cout << ans; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'int main()':
boat.cpp:75:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < ret.size(); ++i)
                   ~~^~~~~~~~~~~~
boat.cpp:77:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (i == ret.size() || ret[i] != ret[i + 1]) {
           ~~^~~~~~~~~~~~~
boat.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seg.size(); ++i) {
                   ~~^~~~~~~~~~~~
boat.cpp:99:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < seg.size(); ++i) {
                   ~~^~~~~~~~~~~~
boat.cpp:106:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int k = 1; k <= a[i].size(); ++k) {
                     ~~^~~~~~~~~~~~~~
boat.cpp:123:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (index < a[i].size() && a[i][index] <= k)
              ~~~~~~^~~~~~~~~~~~~
boat.cpp:126:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int j = index; j < a[i].size(); ++j)
                           ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...