Submission #1169303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169303		Zero_OP	Boat (APIO16_boat)	C++20	100 / 100	1397 ms	20216 KiB

boat

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

typedef long long ll;

using db = double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;

using vi = vector<int>;
using vl = vector<ll>;
using vc = vector<char>;
using vd = vector<db>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
#endif // LOCAL
}

const int mod = 1e9 + 7;
struct mint{
      int v;
      mint(int v = 0) : v(v) {}

      mint& operator += (const mint& o){
            v += o.v;
            if(v >= mod) v -= mod;
            return *this;
      }

      mint& operator -= (const mint& o){
            v -= o.v;
            if(v < 0) v += mod;
            return *this;
      }

      mint& operator *= (const mint& o){
            v = 1LL * v * o.v % mod;
            return *this;
      }

      mint power(ll n) const{
            mint res(1), base(*this);
            for(; n > 0; n >>= 1, base *= base){
                  if(n & 1) res *= base;
            }
            return res;
      }

      mint inv() const {
            return power(mod - 2);
      }

      mint& operator /= (const mint& o){
            return *this *= o.inv();
      }

      friend mint operator + (mint a, const mint& b){ return a += b; }
      friend mint operator - (mint a, const mint& b){ return a -= b; }
      friend mint operator * (mint a, const mint& b){ return a *= b; }
      friend mint operator / (mint a, const mint& b){ return a /= b; }

      friend bool operator == (const mint& a, const mint& b){ return a.v == b.v; }
      friend bool operator != (const mint& a, const mint& b){ return a.v != b.v; }

      friend ostream& operator << (ostream& out, const mint& o){ return out << o.v; }
      friend istream& operator >> (istream& in, mint& o){ return in >> o.v; }
};

const int MAX = 1005;

int N, M, A[MAX], B[MAX], pos[MAX][MAX], num[MAX];
vi v;

mint fact[MAX], ifact[MAX], inv[MAX], dp[MAX][MAX], sum_dp[MAX][MAX];
mint f[MAX][MAX], g[MAX][MAX];

mint C(int n, int k){
      if(n < k || k < 0) return 0;
      if(n <= N) return fact[n] * ifact[n-k] * ifact[k];

      assert(k <= MAX);
      mint result = ifact[k];
      FOR(i, 0, k) result *= mint(n - i);
      return result;
}

void process_prefix_sum(int x){
      sum_dp[x][0] = dp[x][0];
      FOR(i, 1, M) sum_dp[x][i] = sum_dp[x][i-1] + dp[x][i];
}

int main(){
      setIO();

      cin >> N;
      v.pb(0);
      FOR(i, 1, N+1){
            cin >> A[i] >> B[i];
            ++B[i];
            //[A[i], B[i])
            v.pb(A[i]);
            v.pb(B[i]);
      }

      fact[0] = ifact[0] = 1;
      FOR(i, 1, N+1) fact[i] = fact[i-1] * mint(i);
      ifact[N] = fact[N].inv();
      ROF(i, N, 1) ifact[i] = ifact[i+1] * mint(i+1);
      FOR(i, 1, N) inv[i] = ifact[i] * fact[i-1];
      
      sort(all(v)); compact(v);
      M = sz(v)-1;

      FOR(i, 1, M){
            f[i][0] = 1;
            FOR(j, 1, N+1){
                  f[i][j] = C(v[i+1] - v[i], j);
            }

            FOR(j, 2, N+1){
                  FOR(k, 0, j-1){
                        g[i][j] += C(j-2, k) * f[i][k+2];
                  }
            }
      }

      dp[0][0] = 1;
      process_prefix_sum(0);

      FOR(i, 1, N+1){
            A[i] = lower_bound(all(v), A[i]) - v.begin();
            B[i] = lower_bound(all(v), B[i]) - v.begin();

            FOR(j, 0, M){
                  dp[i][j] += dp[i-1][j];
                  if(A[i] <= j && j < B[i]){
                        pos[j][num[j]++] = i;

                        dp[i][j] += sum_dp[i-1][j-1] * mint(v[j+1] - v[j]); //only 1 in range [v[j], v[j+1])
                        FOR(pre, 0, num[j]-1){
                              int p = pos[j][pre], cur = num[j] - pre;
                              ///dp[i][j] = sum_dp[pre-1][j-1] * \sum_{o = 0}^{cur-2} C(cur, o) * C(v[i+1] - v[i], o+2)
                              ///fixed two endpoints
                              dp[i][j] += sum_dp[p-1][j-1] * g[j][cur];
                        }
                  }
            }

            process_prefix_sum(i);
      }

      mint ans = sum_dp[N][M-1] - 1;
      cout << ans << '\n';

      return 0;
}

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