제출 #218157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218157		SamAnd	Boat (APIO16_boat)	C++17	100 / 100	1809 ms	16412 KiB

boat

#include <bits/stdc++.h>
using namespace std;
const int N = 1003;
const int M = 1000000007;

int ast(int x, int n)
{
    int ans = 1;
    while (n)
    {
        if (n % 2 == 1)
            ans = (ans * 1LL * x) % M;
        x = (x * 1LL * x) % M;
        n /= 2;
    }
    return ans;
}

int n;
int l[N], r[N];

vector<int> v;
int C[N][N];
int c[N][N];
int t[N][N];

int dp[N][N];
int p[N][N];
int pp[N][N];

int ans;
void rec(int i)
{
    if (i == n + 1)
    {
        if (!v.empty())
            ++ans;
        return;
    }
    rec(i + 1);
    for (int j = l[i]; j <= r[i]; ++j)
    {
        if (v.empty() || v.back() < j)
        {
            v.push_back(j);
            rec(i + 1);
            v.pop_back();
        }
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &l[i], &r[i]);
        v.push_back(l[i]);
        v.push_back(r[i] + 1);
    }
    sort(v.begin(), v.end());
    vector<int> vv;
    for (int i = 0; i < v.size(); ++i)
    {
        if (!i || v[i] != v[i - 1])
            vv.push_back(v[i]);
    }
    v = vv;
    for (int i = 0; i <= n; ++i)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % M;
    }
    for (int i = 0; i < v.size() - 1; ++i)
    {
        for (int k = 0; k <= n; ++k)
        {
            c[i][k] = 1;
            int f = 1;
            for (int j = 1; j <= k; ++j)
            {
                c[i][k] = (c[i][k] * 1LL * (v[i + 1] - v[i] - j + 1)) % M;
                f = (f * 1LL * j) % M;
            }
            c[i][k] = (c[i][k] * 1LL * ast(f, M - 2)) % M;
        }
        t[i][1] = c[i][1];
        for (int q = 2; q <= n; ++q)
        {
            for (int k = 0; k <= q - 2; ++k)
            {
                t[i][q] = (t[i][q] + c[i][k + 2] * 1LL * C[q - 2][k]) % M;
            }
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < v.size() - 1; ++j)
        {
            if (!(l[i] <= v[j] && v[j + 1] - 1 <= r[i]))
                continue;
            int q = 0;
            for (int k = i; k >= 1; --k)
            {
                if (!(l[k] <= v[j] && v[j + 1] - 1 <= r[k]))
                    continue;
                ++q;
                if (k - 1 == 0 || j - 1 == -1)
                {
                    dp[i][j] = (dp[i][j] + t[j][q]) % M;
                }
                else
                {
                    dp[i][j] = (dp[i][j] + (pp[k - 1][j - 1] + 1) * 1LL * t[j][q]) % M;
                }
            }
        }
        for (int j = 0; j < v.size() - 1; ++j)
        {
            p[i][j] = (p[i - 1][j] + dp[i][j]) % M;
        }
        pp[i][0] = p[i][0];
        for (int j = 1; j < v.size() - 1; ++j)
            pp[i][j] = (pp[i][j - 1] + p[i][j]) % M;
    }
    printf("%d\n", pp[n][v.size() - 2]);
    //v.clear();
    //rec(1);
    //printf("%d\n", ans);
    return 0;
}

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

boat.cpp: In function 'int main()':
boat.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
boat.cpp:76:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size() - 1; ++i)
                     ~~^~~~~~~~~~~~~~
boat.cpp:100:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size() - 1; ++j)
                         ~~^~~~~~~~~~~~~~
boat.cpp:120:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size() - 1; ++j)
                         ~~^~~~~~~~~~~~~~
boat.cpp:125:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < v.size() - 1; ++j)
                         ~~^~~~~~~~~~~~~~
boat.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:58: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