답안 #40681 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40681	2018-02-06T18:49:31 Z	bogdan10bos	Boat (APIO16_boat)	C++14	36 / 100	2000 ms	16208 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];
int cc[4005][1005];

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 = 2; i <= 2 * K - 1; i += 2)
    {
        int lft = nrm.ord[i / 2 - 1];
        int rgt = nrm.ord[i / 2];
        int sz = rgt - lft - 1;

        cmb[0] = 1;
        for(int k = 1; k <= N; k++)
        {
            cmb[k] = (1LL * cmb[k - 1] * (sz - k + 1)) % mod;
            cmb[k] = (1LL * cmb[k] * inv[k]) % mod;
        }

        for(int j = 1; j <= N; j++)
            for(int k = 0; k < j; k++)
                cc[i][j] = (cc[i][j] + (1LL * cmb[k + 1] * C(j - 1, k)) % mod) % mod;
    }

    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 = cc[j][cnt];

                        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:32: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:74:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
boat.cpp:77: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	694 ms	11520 KB	Output is correct
2	Correct	685 ms	11520 KB	Output is correct
3	Correct	688 ms	11524 KB	Output is correct
4	Correct	720 ms	11668 KB	Output is correct
5	Correct	709 ms	11688 KB	Output is correct
6	Correct	700 ms	11780 KB	Output is correct
7	Correct	712 ms	11832 KB	Output is correct
8	Correct	710 ms	11832 KB	Output is correct
9	Correct	703 ms	11832 KB	Output is correct
10	Correct	723 ms	11868 KB	Output is correct
11	Correct	712 ms	11868 KB	Output is correct
12	Correct	688 ms	11868 KB	Output is correct
13	Correct	699 ms	11868 KB	Output is correct
14	Correct	686 ms	11868 KB	Output is correct
15	Correct	739 ms	11868 KB	Output is correct
16	Correct	125 ms	11868 KB	Output is correct
17	Correct	140 ms	11868 KB	Output is correct
18	Correct	135 ms	11868 KB	Output is correct
19	Correct	153 ms	11868 KB	Output is correct
20	Correct	134 ms	11868 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	694 ms	11520 KB	Output is correct
2	Correct	685 ms	11520 KB	Output is correct
3	Correct	688 ms	11524 KB	Output is correct
4	Correct	720 ms	11668 KB	Output is correct
5	Correct	709 ms	11688 KB	Output is correct
6	Correct	700 ms	11780 KB	Output is correct
7	Correct	712 ms	11832 KB	Output is correct
8	Correct	710 ms	11832 KB	Output is correct
9	Correct	703 ms	11832 KB	Output is correct
10	Correct	723 ms	11868 KB	Output is correct
11	Correct	712 ms	11868 KB	Output is correct
12	Correct	688 ms	11868 KB	Output is correct
13	Correct	699 ms	11868 KB	Output is correct
14	Correct	686 ms	11868 KB	Output is correct
15	Correct	739 ms	11868 KB	Output is correct
16	Correct	125 ms	11868 KB	Output is correct
17	Correct	140 ms	11868 KB	Output is correct
18	Correct	135 ms	11868 KB	Output is correct
19	Correct	153 ms	11868 KB	Output is correct
20	Correct	134 ms	11868 KB	Output is correct
21	Execution timed out	2062 ms	16208 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	31 ms	16208 KB	Output is correct
2	Correct	24 ms	16208 KB	Output is correct
3	Correct	24 ms	16208 KB	Output is correct
4	Correct	27 ms	16208 KB	Output is correct
5	Correct	26 ms	16208 KB	Output is correct
6	Correct	29 ms	16208 KB	Output is correct
7	Correct	30 ms	16208 KB	Output is correct
8	Correct	27 ms	16208 KB	Output is correct
9	Correct	27 ms	16208 KB	Output is correct
10	Correct	28 ms	16208 KB	Output is correct
11	Correct	23 ms	16208 KB	Output is correct
12	Correct	22 ms	16208 KB	Output is correct
13	Correct	24 ms	16208 KB	Output is correct
14	Correct	23 ms	16208 KB	Output is correct
15	Correct	27 ms	16208 KB	Output is correct
16	Correct	15 ms	16208 KB	Output is correct
17	Correct	14 ms	16208 KB	Output is correct
18	Correct	13 ms	16208 KB	Output is correct
19	Correct	14 ms	16208 KB	Output is correct
20	Correct	14 ms	16208 KB	Output is correct

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	694 ms	11520 KB	Output is correct
2	Correct	685 ms	11520 KB	Output is correct
3	Correct	688 ms	11524 KB	Output is correct
4	Correct	720 ms	11668 KB	Output is correct
5	Correct	709 ms	11688 KB	Output is correct
6	Correct	700 ms	11780 KB	Output is correct
7	Correct	712 ms	11832 KB	Output is correct
8	Correct	710 ms	11832 KB	Output is correct
9	Correct	703 ms	11832 KB	Output is correct
10	Correct	723 ms	11868 KB	Output is correct
11	Correct	712 ms	11868 KB	Output is correct
12	Correct	688 ms	11868 KB	Output is correct
13	Correct	699 ms	11868 KB	Output is correct
14	Correct	686 ms	11868 KB	Output is correct
15	Correct	739 ms	11868 KB	Output is correct
16	Correct	125 ms	11868 KB	Output is correct
17	Correct	140 ms	11868 KB	Output is correct
18	Correct	135 ms	11868 KB	Output is correct
19	Correct	153 ms	11868 KB	Output is correct
20	Correct	134 ms	11868 KB	Output is correct
21	Execution timed out	2062 ms	16208 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

답안 #40681

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