Submission #41681

#	Time	Username	Problem	Language	Result	Execution time	Memory
41681		gabrielsimoes	Boat (APIO16_boat)	C++14	100 / 100	182 ms	768 KiB

boat

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1000000007;
const int MAXN = 510;

inline ll mod(ll a) { return a %= MOD, a < 0 ? a + MOD : a; }

int n, va[MAXN], vb[MAXN];
vector<int> splits;

ll dp[MAXN], sum[MAXN];
ll inv[MAXN], bin[MAXN];
vector<ll> v;

int main() {
  inv[1] = 1;
  for (int i = 2; i < MAXN; i++) inv[i] = mod(-(MOD / i) * inv[MOD % i]);

  scanf("%d", &n);

  for (int i = 1; i <= n; i++) {
    scanf("%d %d", &va[i], &vb[i]);
    vb[i]++;
    splits.push_back(va[i]);
    splits.push_back(vb[i]);
  }

  sort(splits.begin(), splits.end());
  splits.resize(unique(splits.begin(), splits.end()) - splits.begin());

  for (int i = 1; i <= n; i++) {
    va[i] = (lower_bound(splits.begin(), splits.end(), va[i]) - splits.begin());
    vb[i] = (lower_bound(splits.begin(), splits.end(), vb[i]) - splits.begin());
  }

  for (int split = 1; split < splits.size(); split++) {
    ll len = splits[split] - splits[split - 1];

    sum[0] = 1;
    for (int i = 1; i <= n; i++) sum[i] = (sum[i - 1] + dp[i]) % MOD;
    v.clear();

    bin[0] = 1;
    for (int i = 1; i <= n; i++) {
      if (i <= len + i - 2)
        bin[i] = mod(mod((len + i - 2) * inv[i]) * bin[i - 1]);
      else
        bin[i] = 0;
    }

    for (int i = 1; i <= n; i++) {
      if (va[i] < split && vb[i] >= split) {
        v.push_back(sum[i - 1]);

        for (auto p = v.rbegin(); p != v.rend(); p++) {
          int cnt = (p - v.rbegin()) + 1;
          if (cnt == 1)
            dp[i] += mod((*p) * len);
          else
            dp[i] += mod((*p) * bin[cnt]);
        }

        dp[i] %= MOD;
      }
    }
  }

  ll ans = 0;
  for (int i = 1; i <= n; i++) ans += dp[i];
  printf("%lld\n", ans % MOD);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:38:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int split = 1; split < splits.size(); split++) {
                             ^
boat.cpp:21:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
boat.cpp:24:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &va[i], &vb[i]);
                                   ^

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42