제출 #1165158

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165158		SmuggingSpun	Boat (APIO16_boat)	C++20	31 / 100	1146 ms	46888 KiB

boat

#include<bits/stdc++.h>
#define taskname "A"
using namespace std;
const int lim = 505;
const int LIM = 1e9 + 5;
const int mod = 1e9 + 7;
void add(int& a, int b){
    if((a += b) >= mod){
        a -= mod;
    }
}
int n, a[lim], b[lim];
namespace sub12{
    map<int, int>bit;
    void update(int p, int x){
        for(; p < LIM; p += p & -p){
            add(bit[p], x);
        }
    }
    int get(int p){
        int ans = 0;
        for(; p > 0; p -= p & -p){
            auto it = bit.find(p);
            if(it != bit.end()){
                add(ans, it->second);
            }
        }
        return ans;
    }
    void solve(){
        update(1, 1);
        for(int i = 1; i <= n; i++){
            for(int j = b[i]; j >= a[i]; j--){
                update(j + 1, get(j));
            }
        }
        cout << (get(LIM - 1) + mod - 1) % mod;
    }
}
namespace sub34{
    int power(int a, int b){
        int ans = 1;
        for(; b > 0; b >>= 1, a = 1LL * a * a % mod){
            if(b & 1){
                ans = 1LL * ans * a % mod;
            }
        }
        return ans;
    }
    int inv_gt[lim], pre_Ckn[lim][lim << 1], f[lim][lim << 1];
    vector<pair<int, int>>range(1, make_pair(0, 0));
    void solve(){
        for(int i = inv_gt[0] = 1; i < lim; i++){
            inv_gt[i] = 1LL * inv_gt[i - 1] * i % mod;
        }
        inv_gt[lim - 1] = power(inv_gt[lim - 1], mod - 2) % mod;
        for(int i = lim - 2; i > 1; i--){
            inv_gt[i] = 1LL * inv_gt[i + 1] * (i + 1) % mod;
        } 
        vector<int>S;
        for(int i = 1; i <= n; i++){
            S.emplace_back(a[i]);
            S.emplace_back(b[i]);
        }
        sort(S.begin(), S.end());
        S.resize(unique(S.begin(), S.end()) - S.begin());
        range.emplace_back(1, S[0]);
        for(int i = 1; i < S.size(); i++){
            range.emplace_back(S[i - 1] + 1, S[i]);
        }
        range.emplace_back(S.back() + 1, LIM - 1);
        int N = range.size();
        for(int i = 1; i <= N; i++){
            int len = pre_Ckn[i][1] = range[i].second - range[i].first + 1;
            vector<int>cnt_mask(n + 1, pre_Ckn[i][0] = 0);
            cnt_mask[0] = 1;
            for(int j = 1; j <= n; j++){
                pre_Ckn[i][j + 1] = len;
                for(int k = min(j, len - 1), num = 1; k > 0; k--){
                    add(cnt_mask[k], cnt_mask[k - 1]);
                    add(pre_Ckn[i][j + 1], 1LL * cnt_mask[k] * (num = 1LL * num * (len - k)  % mod) % mod * inv_gt[k + 1] % mod);
                }
            }
        }
        memset(f, -1, sizeof(f));
        function<int(int, int)>dp;
        dp = [&] (int i, int j){
            if(min(i, j) == 0){
                return 1;
            }
            int& ans = f[i][j];
            if(ans != -1){
                return ans;
            }
            ans = ((dp(i, j - 1) + dp(i - 1, j)) % mod - dp(i - 1, j - 1) + mod) % mod;
            if(range[j].first >= a[i] && range[j].second <= b[i]){
                for(int k = i, cnt = 0; k > 0; k--){
                    if(range[j].first >= a[k] && range[j].second <= b[k]){
                        add(ans, 1LL * (pre_Ckn[j][++cnt] - pre_Ckn[j][cnt - 1] + mod) * dp(k - 1, j - 1) % mod);
                    }
                }
            }
            return ans;
        };
        cout << (dp(n, N - 1) + mod - 1) % mod;
    }
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
    }
    int sum = 0;
    for(int i = 1; i <= n; i++){
        if((sum += b[i] - a[i]) > 1000000){
            break;
        }
    }
    if(sum < 1000001){
        sub12::solve();
    }
    else{
        sub34::solve();
    }
}

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

boat.cpp: In function 'int main()':
boat.cpp:111:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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