Submission #218119

#	Time	Username	Problem	Language	Result	Execution time	Memory
218119		SamAnd	Boat (APIO16_boat)	C++17	9 / 100	864 ms	10360 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 dp[N][N];
int p[N][N];
int pp[N][N];

int main()
{
    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());
    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;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < v.size() - 1; ++j)
        {
            int q = 0;
            for (int k = i; k >= 1; --k)
            {
                if (!(l[k] <= v[j] && v[j + 1] - 1 <= r[k]))
                    break;
                ++q;
                if (k - 1 == 0 || j - 1 == -1)
                    dp[i][j] = (dp[i][j] + c[j][q]) % M;
                else
                    dp[i][j] = (dp[i][j] + (pp[k - 1][j - 1] + 1) * 1LL * c[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]);
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:39:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size() - 1; ++i)
                     ~~^~~~~~~~~~~~~~
boat.cpp:55:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size() - 1; ++j)
                         ~~^~~~~~~~~~~~~~
boat.cpp:69:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < v.size() - 1; ++j)
                         ~~^~~~~~~~~~~~~~
boat.cpp:74:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 1; j < v.size() - 1; ++j)
                         ~~^~~~~~~~~~~~~~
boat.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:34: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: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42