제출 #523173

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
523173		blue	Boat (APIO16_boat)	C++17	27 / 100	221 ms	524292 KiB

boat

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
#define sz(x) int(x.size())

const ll mod = 1'000'000'007;

ll mul(ll a, ll b)
{
    return (a*b) % mod;
}

ll ad(ll a, ll b)
{
    return (a+b) % mod;
}

ll sq(ll a)
{
    return mul(a,a);
}

ll pow(ll b, ll e)
{
    if(e == 0) return 1;
    else if(e % 2 == 1) return mul(b, pow(b, e-1));
    else return sq(pow(b, e/2));
}

ll get_inv(ll a)
{
    return pow(a, mod-2);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    ll a[1+N], b[1+N];


    map<ll, ll> values;

    for(int i = 1; i <= N; i++)
    {
        cin >> a[i] >> b[i];
        b[i]++;

        values[a[i]] = 0;
        values[b[i]] = 0;
    }

    values[0] = 0;
    values[1] = 0;


    vll ep;

    for(auto& z : values) ep.push_back(z.first);

    int ct = sz(ep) - 1;

    vll blocksize(1+ct);
    blocksize[0] = 0;
    for(int i = 1; i <= ct; i++)
        blocksize[i] = ep[i] - ep[i-1];

    
    int x[1+N], y[1+N];


    // for(int i = 0; i <= ct; i++) cerr << i << " : " << ep[i] << ' ' << blocksize[i] << '\n';

    for(int i = 1; i <= N; i++)
    {
        x[i] = 0;
        int lo = 1, hi = ct;
        while(lo != hi)
        {
            int mid = (lo+hi)/2 + 1;
            if(ep[mid] <= a[i])
                lo = mid;
            else
                hi = mid-1;
        }
        x[i] = lo + 1;

        y[i] = 0;
        lo = 1, hi = ct;
        while(lo != hi)
        {
            int mid = (lo+hi)/2+1;
            if(ep[mid] <= b[i])
                lo = mid;
            else
                hi = mid-1;
        }
        y[i] = lo;
    }


    ll*** DP = new ll**[1+N];
    for(int i = 0; i <= N; i++)
    {
        DP[i] = new ll*[1+ct];
        for(int j = 0; j <= ct; j++)
        {
            DP[i][j] = new ll[1+N];
            for(int k = 0; k <= N; k++) DP[i][j][k] = 0;
        }
    }


    ll inv[1+N];
    for(int i = 1; i <= N; i++) inv[i] = get_inv(i);

    vvll DPsum(1+N, vll(1+ct, 0)); 

    // cerr << "!" <<  x[1] << ' ' << y[1] << '\n';
    for(int j = x[1]; j <= y[1]; j++)
    {
        DPsum[1][j] = ad(DPsum[1][j], blocksize[j]);
        DP[1][j][1] = blocksize[j];   
    }


    for(int i = 2; i <= N; i++)
    {
        for(int j = 1; j <= ct; j++)
        {
            for(int k = 1; k <= i; k++)
            {
                DP[i][j][k] = DP[i-1][j][k];

                if(x[i] <= j && j <= y[i])
                {
                    if(j == 1 && k == 1)
                    {
                        ;//DP[i][1][1] = blocksize[j] * 
                    }
                    else if(j == 1)
                    {
                        ;
                    }
                    else if(k == 1)
                    {
                        ll curr = 1;

                        for(int j2 = 1; j2 < j; j2++)
                            curr = ad(curr, DPsum[i-1][j2]);

                        DP[i][j][1] = ad(DP[i][j][1], mul(curr, blocksize[j]));
                    }
                    else
                    {
                        if(k <= blocksize[j])
                            DP[i][j][k] = ad(DP[i][j][k], mul(DP[i-1][j][k-1], mul(blocksize[j] - k + 1, inv[k])));
                    }
                }

                DPsum[i][j] = ad(DPsum[i][j], DP[i][j][k]);
            }
        }
    }

    ll res = 0;
    for(int j = 1; j <= ct; j++)
        res = ad(res, DPsum[N][j]);

    cout << res << '\n';
}

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