oj.uz

Submission #218119

# Submission time Handle Problem Language Result Execution time Memory
218119 2020-04-01T09:32:57 Z SamAnd Boat (APIO16_boat) C++17
9 / 100
 864 ms 10360 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 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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 9976 KB Output is correct
2 Correct 857 ms 9976 KB Output is correct
3 Correct 851 ms 9848 KB Output is correct
4 Correct 842 ms 9976 KB Output is correct
5 Correct 835 ms 9848 KB Output is correct
6 Correct 854 ms 10236 KB Output is correct
7 Correct 860 ms 10360 KB Output is correct
8 Correct 835 ms 10104 KB Output is correct
9 Correct 843 ms 10104 KB Output is correct
10 Correct 838 ms 10232 KB Output is correct
11 Correct 835 ms 10232 KB Output is correct
12 Correct 845 ms 10220 KB Output is correct
13 Correct 856 ms 10104 KB Output is correct
14 Correct 864 ms 10256 KB Output is correct
15 Correct 835 ms 10300 KB Output is correct
16 Correct 846 ms 9848 KB Output is correct
17 Correct 860 ms 9976 KB Output is correct
18 Correct 860 ms 9976 KB Output is correct
19 Correct 843 ms 9864 KB Output is correct
20 Correct 847 ms 9948 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 9976 KB Output is correct
2 Correct 857 ms 9976 KB Output is correct
3 Correct 851 ms 9848 KB Output is correct
4 Correct 842 ms 9976 KB Output is correct
5 Correct 835 ms 9848 KB Output is correct
6 Correct 854 ms 10236 KB Output is correct
7 Correct 860 ms 10360 KB Output is correct
8 Correct 835 ms 10104 KB Output is correct
9 Correct 843 ms 10104 KB Output is correct
10 Correct 838 ms 10232 KB Output is correct
11 Correct 835 ms 10232 KB Output is correct
12 Correct 845 ms 10220 KB Output is correct
13 Correct 856 ms 10104 KB Output is correct
14 Correct 864 ms 10256 KB Output is correct
15 Correct 835 ms 10300 KB Output is correct
16 Correct 846 ms 9848 KB Output is correct
17 Correct 860 ms 9976 KB Output is correct
18 Correct 860 ms 9976 KB Output is correct
19 Correct 843 ms 9864 KB Output is correct
20 Correct 847 ms 9948 KB Output is correct
21 Incorrect 855 ms 10172 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 2304 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 836 ms 9976 KB Output is correct
2 Correct 857 ms 9976 KB Output is correct
3 Correct 851 ms 9848 KB Output is correct
4 Correct 842 ms 9976 KB Output is correct
5 Correct 835 ms 9848 KB Output is correct
6 Correct 854 ms 10236 KB Output is correct
7 Correct 860 ms 10360 KB Output is correct
8 Correct 835 ms 10104 KB Output is correct
9 Correct 843 ms 10104 KB Output is correct
10 Correct 838 ms 10232 KB Output is correct
11 Correct 835 ms 10232 KB Output is correct
12 Correct 845 ms 10220 KB Output is correct
13 Correct 856 ms 10104 KB Output is correct
14 Correct 864 ms 10256 KB Output is correct
15 Correct 835 ms 10300 KB Output is correct
16 Correct 846 ms 9848 KB Output is correct
17 Correct 860 ms 9976 KB Output is correct
18 Correct 860 ms 9976 KB Output is correct
19 Correct 843 ms 9864 KB Output is correct
20 Correct 847 ms 9948 KB Output is correct
21 Incorrect 855 ms 10172 KB Output isn't correct
22 Halted 0 ms 0 KB -