제출 #1155266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155266		Sang	Boat (APIO16_boat)	C++20	100 / 100	1349 ms	15836 KiB

boat

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

//#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

int n, L[505], R[505], dp[505][5005], pref[505][5005], dp2[5005][505], inv[505];

int Pow(int a, int b){
    if (b == 0) return 1;
    int t = Pow(a, b/2);
    t = (t * 1ll*  t)%MOD;
    if (b%2 == 0) return t;
    return (t * 1ll * a)%MOD;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin >> n ;
    FOR (i, 1, n) {
        cin >> L[i] >> R[i];
    }
    map<int, int> dd;
    vi vals;
    FOR (i, 1, n){
        int x = R[i];
        vals.pb(x);
        vals.pb(L[i]);
        if (x - 1) vals.pb(x-1);
        vals.pb(x+1);

    }
    sort(ALL(vals));
    vals.resize(unique(ALL(vals)) - vals.begin());
    int m = (int)vals.size();
    FOR (i, 1, n){
        L[i] = upper_bound(ALL(vals), L[i]) - vals.begin();
        R[i] = upper_bound(ALL(vals), R[i]) - vals.begin();
    }
    FOR (i, 1, 504) inv[i] = Pow(i, MOD - 2);
    dp[0][m + 1] = 1;
    FOR (i, 1, n){
        FORD(j, i-1, 0){
            FOR (k, L[i], R[i] - 1){
                int cnt = vals[k]-vals[k-1];
                dp[i][k] = (dp[i][k] + (pref[j][k-1] * 1ll * cnt)%MOD)%MOD;
                if (k >= R[j]){
                    dp[i][k] = (dp[i][k] + (dp[j][m+1] * 1ll * (cnt - (k == R[j])))%MOD)%MOD;
                }
            }
            dp[i][m+1] = (dp[i][m+1] + pref[j][R[i]-1])%MOD;
            if (R[i] > R[j]){
                dp[i][m+1] = (dp[i][m+1] + dp[j][m+1])%MOD;
            }
        }
        FOR (k, L[i], R[i] - 1){
            int cnt = vals[k] - vals[k-1];
            int ans = 0;
            FORD(j, min(n, cnt), 2){
                int t = inv[j] * 1ll * (cnt - j + 1)%MOD;
                ans = (ans + dp2[k][j-1] *1ll* t%MOD)%MOD;
                dp2[k][j] = (dp2[k][j] + dp2[k][j-1] *1ll* t%MOD)%MOD;
            }
            dp2[k][1] = (dp2[k][1] + dp[i][k])%MOD;
            dp[i][k] = (dp[i][k] + ans)%MOD;
        }
        FOR (j, 1, m) pref[i][j] = (pref[i][j-1] + dp[i][j])%MOD;
    }
    /*
    3
    1 5
    5 10
    5 15
    */
//    FOR (i, 1, n){
//        FOR (j, 1, m + 1) cout << dp[i][j] << ' ';
//        cout << '\n';
//    }
    int ans = 0;
    FOR (i, 1, n){
        ans = (ans + dp[i][m+1])%MOD;
        FOR (k, L[i], R[i]-1) ans = (ans + dp[i][k])%MOD;
    }
    cout << ans;


    return 0;
}

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

boat.cpp: In function 'int main()':
boat.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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