제출 #631558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631558		CDuong	Boat (APIO16_boat)	C++14	0 / 100	2 ms	468 KiB

boat

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
*/
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define endl '\n'
#define pii pair<int, int>
using namespace std;
const int mxN = 505;
const int mod = 1e9 + 7;
int n, ans, fact[mxN], revfact[mxN], dp[2 * mxN][mxN], pref[2 * mxN][mxN];
pii p[mxN];
vector<int> v;
vector<pii> seg;
int binpow(int x, int y){
    int res = 1;
    while(y != 0){
        if(y % 2 == 1) res = (res * x) % mod;
        x = (x * x) % mod;
        y /= 2;
    }
    return res;
}
int calc(){
    fact[0] = 1;
    for(int i = 1; i < 505; ++i){
        fact[i] = (fact[i - 1] * i) % mod;
    }
    for(int i = 0; i < 505; ++i){
        revfact[i] = binpow(fact[i], mod - 2);
        //cout << fact[i] << " " << revfact[i] << endl;
    }
}
int rCk(int r, int k){
    int tmp = (fact[k] * revfact[r]) % mod;
    tmp = (tmp * revfact[k - r]) % mod;
    //cout << r << " " << k << " " << tmp << endl;
    return tmp;
}
bool check(pii x, pii y){
    if(x.ff >= y.ff && x.ss <= y.ss) return true;
    return false;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    //freopen("Bai3.inp", "r", stdin);
    //freopen("Bai3.out", "w", stdout);
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> p[i].ff >> p[i].ss;
        v.pb(p[i].ff);
        v.pb(p[i].ss + 1);
    }
    calc();
    sort(v.begin(), v.end());
    vector<int>::iterator it = unique(v.begin(), v.end());
    v.resize(distance(v.begin(), it));
    seg.pb({0, 0});
    for(int i = 1; i < v.size(); ++i){
        seg.pb({v[i - 1], v[i] - 1});
        //cout << seg[i - 1].ff << " " << seg[i - 1].ss << endl;
    }
    dp[0][0] = ans = 1;
    //cout << rCk(1, 1) << endl;
    for(int i = 1; i < seg.size(); ++i){
        dp[i][0] = pref[i][0] = 1;
        int dis = seg[i].ss - seg[i].ff + 1;
        //cout << "seg: " << i << " " << seg[i].ff << " " << seg[i].ss << endl;
        for(int j = 1; j <= n; ++j){
            dp[i][j] += pref[i - 1][j];
            int k = j;
            while(k >= 1 && check(seg[i], p[k])){
                int tmp = rCk(j - k + 1, dis);
                tmp = (tmp * dp[i - 1][k - 1]);
                //cout << i << " " << j << " " << k << " " << tmp << endl;
                dp[i][j] += tmp;
                k--;
            }
            pref[i][j] = dp[i][j] + pref[i - 1][j];
            //cout << i << " " << j << " " << dp[i][j] << endl;
            if(i == seg.size() - 1) ans += dp[i][j];
        }
    }
    cout << ans << endl;
}

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

boat.cpp: In function 'long long int calc()':
boat.cpp:39:1: warning: no return statement in function returning non-void [-Wreturn-type]
   39 | }
      | ^
boat.cpp: In function 'int main()':
boat.cpp:66:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for(int i = 1; i < v.size(); ++i){
      |                    ~~^~~~~~~~~~
boat.cpp:72:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i = 1; i < seg.size(); ++i){
      |                    ~~^~~~~~~~~~~~
boat.cpp:88:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             if(i == seg.size() - 1) ans += dp[i][j];
      |                ~~^~~~~~~~~~~~~~~~~

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