oj.uz

Submission #218141

# Submission time Handle Problem Language Result Execution time Memory
218141 2020-04-01T10:18:28 Z SamAnd Boat (APIO16_boat) C++17
0 / 100
 2000 ms 13816 KB 
#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 pc[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());
    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;
            if (k > 1)
                pc[i][k] = (pc[i][k - 1] + c[i][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)
                {
                    if (i == k)
                        dp[i][j] = (dp[i][j] + c[j][q]) % M;
                    else
                        dp[i][j] = (dp[i][j] + pc[j][q]) % M;
                }
                else
                {
                    if (i == k)
                        dp[i][j] = (dp[i][j] + (pp[k - 1][j - 1] + 1) * 1LL * c[j][q]) % M;
                    else
                        dp[i][j] = (dp[i][j] + (pp[k - 1][j - 1] + 1) * 1LL * pc[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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Execution timed out 2092 ms 13816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2092 ms 13816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 3072 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2092 ms 13816 KB Time limit exceeded
2 Halted 0 ms 0 KB -