제출 #736252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
736252		vjudge1	Boat (APIO16_boat)	C++17	9 / 100	230 ms	7140 KiB

boat

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

int f[1000][501];
int a[500], b[500], cnt[1000];
int fact[501], ifact[501];
const int MOD = 1e9 + 7;
int lC[1000][501];
int C[501][501];
int g[501][1000];

inline int Power(int a, int b) {
        int64_t res = 1;
        for (; b; b >>= 1, a = 1ll * a * a % MOD) {
                if (b & 1) (res *= a) %= MOD;
        }
        return res;
}

int main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n;
        cin >> n;
        /// small nCk
        for (int i = 0; i <= n; i++) C[i][0] = C[i][i] = 1;
        for (int i = 0; i <= n; i++) {
                for (int j = 1; j < i; j++) {
                        C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
                        if (C[i][j] >= MOD) C[i][j] -= MOD;
                }
        }
        /// calc ifact
        fact[0] = 1;
        for (int i = 1; i <= n; i++) fact[i] = 1ll * fact[i - 1] * i % MOD;
        ifact[n] = Power(fact[n], MOD - 2);
        for (int i = n; i >= 1; i--) ifact[i - 1] = 1ll * ifact[i] * i % MOD;
        /// input
        for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
        vector<int> point;
        point.reserve(n * 2);
        for (int i = 0; i < n; i++) point.emplace_back(a[i]);
        for (int i = 0; i < n; i++) point.emplace_back(b[i] + 1);
        sort(point.begin(), point.end());
        point.resize(unique(point.begin(), point.end()) - point.begin());
        assert(point.size() <= n * 2);
        int m = point.size() - 1;
        vector<int> range(m);
        for (int i = 0; i < m; i++) range[i] = point[i + 1] - point[i];
        for (int i = 0; i < n; i++) a[i] = lower_bound(point.begin(), point.end(), a[i]) - point.begin();
        for (int i = 0; i < n; i++) b[i] = lower_bound(point.begin(), point.end(), b[i] + 1) - point.begin();
        for (int i = 0; i < n; i++) {
                cnt[a[i]]++;
                cnt[b[i]]--;
        }
        for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        /// large nCk
        for (int i = 0; i < m; i++) {
                lC[i][0] = 1;
                for (int j = 1, k = range[i]; j <= cnt[i]; j++, k--) lC[i][j] = 1ll * lC[i][j - 1] * k % MOD;
                for (int j = 1; j <= cnt[i]; j++) lC[i][j] = 1ll * lC[i][j] * ifact[j] % MOD;
        }
        /// calc f
        for (int i = 0; i < m; i++) {
                for (int j = 1; j <= cnt[i]; j++) {
                        for (int k = 1; k <= j; k++) {
                                f[i][j] += 1ll * lC[i][j] * C[cnt[i] - 1][k - 1] % MOD;
                                if (f[i][j] >= MOD) f[i][j] -= MOD;
                        }
                }
        }
        for (int i = 0; i < m; i++) g[0][i] = 1;
        for (int i = 0; i < n; i++) {
                for (int j = a[i]; j < b[i]; j++) {
                        for (int k = i, z = 0; k >= 0; k--) {
                                z += a[k] <= j && j < b[k];
                                if (z > range[j]) z--;
                                int x = j ? g[k][j - 1] : (k == 0);
                                if (x != 0) {
                                        g[i + 1][j] += 1ll * x * f[j][z] % MOD;
                                        if (g[i + 1][j] >= MOD) g[i + 1][j] -= MOD;
                                }
                        }
                }

                for (int j = a[i] + 1; j < m; j++) {
                        g[i + 1][j] += g[i + 1][j - 1];
                        if (g[i + 1][j] >= MOD) g[i + 1][j] -= MOD;
                }
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
                res += g[i][m - 1];
                if (res >= MOD) res -= MOD;
        }
        cout << res;
}

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

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from boat.cpp:1:
boat.cpp: In function 'int main()':
boat.cpp:46:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         assert(point.size() <= n * 2);
      |                ~~~~~~~~~~~~~^~~~~~~~

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