제출 #113983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113983		patrikpavic2	Boat (APIO16_boat)	C++17	100 / 100	816 ms	18396 KiB

boat

#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll;

const int N = 1005;
const int MOD = 1e9 + 7;

inline int add(const int &A, const int &B){
    if(A + B >= MOD) return A + B - MOD;
    return A + B;
}

inline int mul(const int &A, const int &B){
    return (ll)A * B % MOD;
}

inline int sub(const int &A, const int &B){
    if(A - B < 0) return A - B + MOD;
    return A - B;
}

inline int eks(const int &A, int B){
    int ans = 1, bs = A;
    for(;B;B >>= 1){
        if(B & 1)
            ans = mul(ans, bs);
        bs = mul(bs, bs);
    }
    return ans;
}

int n, inv[N], fak[N];
int ch[N][N], L[N], R[N], b_L[N], b_R[N], m, in[N][N], ch2[N][N], pos[N][N], dp[N][N];
vector < int > v;

void precompute(){
    fak[0] = 1; inv[0] = 1;
    for(int i = 1;i < N;i++){
        fak[i] = mul(i, fak[i - 1]);
        inv[i] = eks(fak[i], MOD - 2);
    }
    for(int i = 0;i < N;i++){
        ch[i][i] = 1; ch[i][0] = 1;
    }
    for(int i = 1;i < N;i++){
        for(int j = 1;j < i;j++){
            ch[i][j] = add(ch[i - 1][j], ch[i - 1][j - 1]);
        }
    }
}

int f(int bl, int i){
    if(bl == m) return 1;
    if(dp[bl][i] != -1) return dp[bl][i];
    int ret = f(bl + 1, i);
    int cnt = 0;
    for(int j = i;j < n;j++){
        cnt += in[j][bl];
        if(in[j][bl]){
            ret = add(ret, mul(f(bl + 1, j + 1), pos[bl][cnt]));
        }
    }
    return dp[bl][i] = ret;
}

int brute(int i,int lst){
    if(i == n) return 1;
    int ret = brute(i + 1, lst);
    for(int j = max(L[i], lst + 1);j <= R[i];j++)
        ret += brute(i + 1, j);
    return ret;
}

int main(){
    memset(dp, -1, sizeof(dp));
    precompute();
    scanf("%d", &n);
    for(int i = 0;i < n;i++){
        scanf("%d%d", L + i, R + i);
        v.PB(L[i]); v.PB(R[i] + 1);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    m = v.size() - 1;
    for(int i = 0;i < m;i++){
        b_L[i] = v[i]; b_R[i] = v[i + 1] - 1;
        //printf("BLOK %d : %d %d\n", i, b_L[i], b_R[i]);
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if(L[i] <= b_L[j] && b_R[j] <= R[i])
                in[i][j] = 1;
        }
    }
    for(int i = 0;i < m;i++){
        int len = b_R[i] - b_L[i] + 1;
        int cur = len; ch2[i][0] = 1;
        for(int j = 1;j <= n;j++){
            ch2[i][j] = mul(cur, inv[j]);
            //printf("%d povrh %d = %d\n", len, j, ch2[i][j]);
            cur = mul(cur, len - j);
        }
    }
    for(int i = 0;i < m;i++){
        for(int j = 1;j <= n;j++){
            for(int k = 0;k < j;k++){
                pos[i][j] = add(pos[i][j], mul(ch2[i][k + 1], ch[j - 1][k]));
            }
            //printf("pos[%d][%d] = %d\n", i, j, pos[i][j]);
        }
    }
    printf("%d\n", sub(f(0,0), 1));
  //  printf("%d\n", sub(brute(0,0), 1));
}

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

boat.cpp: In function 'int main()':
boat.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", L + i, R + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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