제출 #500518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500518		doowey	Boat (APIO16_boat)	C++14	36 / 100	504 ms	11812 KiB

boat

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 505;
const int M = N * 4;
const int MOD = (int)1e9 + 7;
int L[N], R[N];

int C[M][N];
int I[N][N];

int fin[M][N];

int powr(int n, int k){
    if(k == 0) return 1;
    int p = powr(n, k / 2);
    p = (p * 1ll * p) % MOD;
    if(k % 2 == 1) p = (p * 1ll * n) % MOD;
    return p;
}

void add(int &a, int b){
    a += b;
    if(a >= MOD) a -= MOD;
    else if(a < 0) a += MOD;
}

int dp[N][M];
int dif[N];
int S[N];

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n;
    cin >> n;
    vector<int> pp;
    for(int i = 1; i <= n; i ++ ){
        cin >> L[i] >> R[i];
        pp.push_back(L[i]);
        pp.push_back(R[i]);
    }
    sort(pp.begin(), pp.end());
    pp.resize(unique(pp.begin(), pp.end()) - pp.begin());
    vector<pii> segm;
    for(int i = 0 ; i < pp.size(); i ++ ){
        segm.push_back(mp(pp[i], pp[i]));
        if(i + 1 < pp.size() && pp[i] + 1 <= pp[i + 1] - 1){
            segm.push_back(mp(pp[i] + 1, pp[i + 1] - 1));
        }
    }
    int m = segm.size();
    for(int i = 0; i < N ;i ++ ){
        I[i][0] = 1;
    }
    for(int k = 1; k < N ; k ++ ){
        for(int i = 1; i < N ; i ++ ){
            add(I[i][k], I[i-1][k]);
            add(I[i][k], I[i-1][k-1]);
        }
    }
    int sz;
    int P, Q;
    int inv;
    int cum;
    for(int i = 0 ; i < m ; i ++ ){
        sz = segm[i].se - segm[i].fi + 1;
        P = Q = 1;
        for(int j = 1; j <= n; j ++ ){
            if(j > sz) break;
            P = (P * 1ll * (sz - j + 1)) % MOD;
            Q = (Q * 1ll * j) % MOD;
            inv = powr(Q, MOD - 2);
            C[i][j] = (P * 1ll * inv) % MOD;
        }
        if(sz == 1){
            for(int j = 1; j <= n; j ++ ){
                fin[i][j] = j;
            }
        }
        else{
            for(int j = 1; j <= n; j ++ ){
                for(int v = 1; v <= j; v ++ ){
                    add(fin[i][j], (C[i][v] * 1ll * I[j][v]) % MOD);
                }
            }
        }
        for(int j = n; j >= 1; j -- ){
            add(fin[i][j], -fin[i][j-1]);
        }
    }

    int tl, tr;
    int mm;
    int side;
    int res = 0;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 0 ; j < m ; j ++ ){
            tl = segm[j].fi;
            tr = segm[j].se;
            if(L[i] <= tl && tr <= R[i]){
                if(tl == tr){
                    if(j) add(dp[i][j], S[j-1]);
                    add(dp[i][j], +1);
                }
                else{
                    mm = 0;

                    for(int v = i; v >= 1; v -- ){

                        if(L[v] <= tl && tr <= R[v]) mm ++ ;
                        side = 0;
                        if(j > 0) add(side, dp[v - 1][j - 1]);
                        if(v == 1) add(side, 1);
                        add(dp[i][j], (side * 1ll * fin[j][mm]) % MOD);
                    }
                }
            }
            add(res, dp[i][j]);
            if(j)
                add(dp[i][j], dp[i][j-1]);
        }
        for(int j = 0 ; j < m ; j ++ ){
            add(S[j],dp[i][j]);
        }
    }

    cout << res << "\n";
    return 0;
}

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

boat.cpp: In function 'int main()':
boat.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i = 0 ; i < pp.size(); i ++ ){
      |                     ~~^~~~~~~~~~~
boat.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         if(i + 1 < pp.size() && pp[i] + 1 <= pp[i + 1] - 1){
      |            ~~~~~~^~~~~~~~~~~
boat.cpp:74:9: warning: unused variable 'cum' [-Wunused-variable]
   74 |     int cum;
      |         ^~~

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