답안 #40680 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40680	2018-02-06T18:42:40 Z	bogdan10bos	Boat (APIO16_boat)	C++14	36 / 100	2000 ms	8684 KB

boat

#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

const int mod = 1e9 + 7;

int N, K;
int a[1005], b[1005], st[1005], dr[1005];
int dp[1005][4005], sum[1005][4005];  /// primele i, ultimul este in intervalul j
int fct[100005], ifct[100005], inv[100005];
int cmb[100005];

class Normalize
{
public:
    map<int, int> mp;
    vector<int> ord;

    void add(int x)
    {
        if(mp.count(x)) return;
        ord.push_back(x);
        mp[x];
    }

    void normalize()
    {
        sort(ord.begin(), ord.end());
        for(int i = 0; i < ord.size(); i++)
            mp[ ord[i] ] = i;
    }

    int get(int x) { return mp[x]; }
}nrm;

int power(int x, int y)
{
    if(y <= 0)  return 1;
    int ans = power( (1LL * x * x) % mod, y >> 1 );
    if(y & 1)   ans = (1LL * x * ans) % mod;
    return ans;
}

void pre(int K)
{
    fct[0] = 1;
    for(int i = 1; i <= K; i++) fct[i] = (1LL * fct[i - 1] * i) % mod;
    ifct[K] = power(fct[K], mod - 2);
    for(int i = K - 1; i >= 0; i--) ifct[i] = (1LL * ifct[i + 1] * (i + 1)) % mod;

    for(int i = 1; i <= K; i++) inv[i] = power(i, mod - 2);
}

int C(int N, int K)
{
    if(K > N)   return 0;
    int ans = (1LL * fct[N] * ifct[K]) % mod;
    ans = (1LL * ans * ifct[N - K]) % mod;
    return ans;
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
    #endif

    pre(1e4);

    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
    {
        scanf("%d%d", &a[i], &b[i]);
        nrm.add(a[i]);
        nrm.add(b[i]);
    }
    nrm.normalize();
    for(int i = 1; i <= N; i++)
    {
        st[i] = nrm.get(a[i]);
        dr[i] = nrm.get(b[i]);
    }
    K = nrm.ord.size();

    for(int i = 0; i <= 2 * K - 1; i++) dp[0][i] = sum[0][i] = 1;

    int ans = 0;

    for(int i = 1; i <= N; i++)
    {
        sum[i][0] = sum[i - 1][0];
        for(int j = 1; j <= 2 * K - 1; j++)
        {
            dp[i][j] = dp[i][j - 1];
            if(j & 1)
            {
                int x = nrm.ord[j / 2];
                if(a[i] <= x && x <= b[i])
                    dp[i][j] = (dp[i][j] + sum[i - 1][j - 1]) % mod;
            }
            else
            {
                int lft = nrm.ord[j / 2 - 1];
                int rgt = nrm.ord[j / 2];
                int sz = rgt - lft - 1;

                if(a[i] <= lft && rgt <= b[i])
                {
                    cmb[0] = 1;
                    for(int k = 1; k <= i; k++)
                    {
                        cmb[k] = (1LL * cmb[k - 1] * (sz - k + 1)) % mod;
                        cmb[k] = (1LL * cmb[k] * inv[k]) % mod;
                    }

                    int cnt = 0;
                    for(int k = i; k > 0; k--)
                    {
                        if(a[k] <= lft && rgt <= b[k])
                            cnt++;

                        int ans = 0;
                        for(int o = 0; o < cnt; o++)
                            ans = (ans + (1LL * cmb[o + 1] * C(cnt - 1, o)) % mod) % mod;

                        dp[i][j] += (1LL * dp[k - 1][j - 1] * ans) % mod;
                        dp[i][j] %= mod;
                    }
                }
            }
            sum[i][j] = (sum[i - 1][j] + dp[i][j]) % mod;
        }
        ans = (ans + dp[i][2 * K - 1]) % mod;
    }
    printf("%d\n", ans);

    return 0;
}

Compilation message

boat.cpp: In member function 'void Normalize::normalize()':
boat.cpp:31:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < ord.size(); i++)
                          ^
boat.cpp: In function 'int main()':
boat.cpp:73:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
boat.cpp:76:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a[i], &b[i]);
                                    ^

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	8440 KB	Output is correct
2	Correct	15 ms	8544 KB	Output is correct
3	Correct	13 ms	8616 KB	Output is correct
4	Correct	13 ms	8616 KB	Output is correct
5	Correct	13 ms	8616 KB	Output is correct
6	Correct	14 ms	8632 KB	Output is correct
7	Correct	14 ms	8648 KB	Output is correct
8	Correct	21 ms	8684 KB	Output is correct
9	Correct	13 ms	8684 KB	Output is correct
10	Correct	14 ms	8684 KB	Output is correct
11	Correct	17 ms	8684 KB	Output is correct
12	Correct	13 ms	8684 KB	Output is correct
13	Correct	14 ms	8684 KB	Output is correct
14	Correct	14 ms	8684 KB	Output is correct
15	Correct	13 ms	8684 KB	Output is correct
16	Correct	9 ms	8684 KB	Output is correct
17	Correct	9 ms	8684 KB	Output is correct
18	Correct	9 ms	8684 KB	Output is correct
19	Correct	9 ms	8684 KB	Output is correct
20	Correct	9 ms	8684 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	8440 KB	Output is correct
2	Correct	15 ms	8544 KB	Output is correct
3	Correct	13 ms	8616 KB	Output is correct
4	Correct	13 ms	8616 KB	Output is correct
5	Correct	13 ms	8616 KB	Output is correct
6	Correct	14 ms	8632 KB	Output is correct
7	Correct	14 ms	8648 KB	Output is correct
8	Correct	21 ms	8684 KB	Output is correct
9	Correct	13 ms	8684 KB	Output is correct
10	Correct	14 ms	8684 KB	Output is correct
11	Correct	17 ms	8684 KB	Output is correct
12	Correct	13 ms	8684 KB	Output is correct
13	Correct	14 ms	8684 KB	Output is correct
14	Correct	14 ms	8684 KB	Output is correct
15	Correct	13 ms	8684 KB	Output is correct
16	Correct	9 ms	8684 KB	Output is correct
17	Correct	9 ms	8684 KB	Output is correct
18	Correct	9 ms	8684 KB	Output is correct
19	Correct	9 ms	8684 KB	Output is correct
20	Correct	9 ms	8684 KB	Output is correct
21	Execution timed out	2024 ms	8684 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	61 ms	8684 KB	Output is correct
2	Correct	49 ms	8684 KB	Output is correct
3	Correct	63 ms	8684 KB	Output is correct
4	Correct	64 ms	8684 KB	Output is correct
5	Correct	74 ms	8684 KB	Output is correct
6	Correct	151 ms	8684 KB	Output is correct
7	Correct	150 ms	8684 KB	Output is correct
8	Correct	152 ms	8684 KB	Output is correct
9	Correct	154 ms	8684 KB	Output is correct
10	Correct	150 ms	8684 KB	Output is correct
11	Correct	70 ms	8684 KB	Output is correct
12	Correct	45 ms	8684 KB	Output is correct
13	Correct	49 ms	8684 KB	Output is correct
14	Correct	58 ms	8684 KB	Output is correct
15	Correct	65 ms	8684 KB	Output is correct
16	Correct	30 ms	8684 KB	Output is correct
17	Correct	27 ms	8684 KB	Output is correct
18	Correct	29 ms	8684 KB	Output is correct
19	Correct	27 ms	8684 KB	Output is correct
20	Correct	36 ms	8684 KB	Output is correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	8440 KB	Output is correct
2	Correct	15 ms	8544 KB	Output is correct
3	Correct	13 ms	8616 KB	Output is correct
4	Correct	13 ms	8616 KB	Output is correct
5	Correct	13 ms	8616 KB	Output is correct
6	Correct	14 ms	8632 KB	Output is correct
7	Correct	14 ms	8648 KB	Output is correct
8	Correct	21 ms	8684 KB	Output is correct
9	Correct	13 ms	8684 KB	Output is correct
10	Correct	14 ms	8684 KB	Output is correct
11	Correct	17 ms	8684 KB	Output is correct
12	Correct	13 ms	8684 KB	Output is correct
13	Correct	14 ms	8684 KB	Output is correct
14	Correct	14 ms	8684 KB	Output is correct
15	Correct	13 ms	8684 KB	Output is correct
16	Correct	9 ms	8684 KB	Output is correct
17	Correct	9 ms	8684 KB	Output is correct
18	Correct	9 ms	8684 KB	Output is correct
19	Correct	9 ms	8684 KB	Output is correct
20	Correct	9 ms	8684 KB	Output is correct
21	Execution timed out	2024 ms	8684 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

답안 #40680

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
0 / 42.0