답안 #40674 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40674	2018-02-06T18:11:17 Z	bogdan10bos	Boat (APIO16_boat)	C++14	9 / 100	463 ms	11940 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];

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])
                {
                    int cnt = 0;
                    int sum = 0;
                    int c = 1;
                    for(int k = i; k > 0; k--)
                    {
                        if(a[k] <= lft && rgt <= b[k])
                        {
                            cnt++;
                            if(cnt <= sz)
                            {
                                c = (1LL * c * (sz - cnt + 1)) % mod;
                                c = (1LL * c * inv[cnt]) % mod;
                                sum = (sum + c) % mod;
                            }
                        }
                        dp[i][j] += (1LL * dp[k - 1][j - 1] * sum) % 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:30: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:72:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
boat.cpp:75: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	16 ms	8440 KB	Output is correct
2	Correct	13 ms	8440 KB	Output is correct
3	Correct	15 ms	8488 KB	Output is correct
4	Correct	14 ms	8688 KB	Output is correct
5	Correct	14 ms	8688 KB	Output is correct
6	Correct	14 ms	8688 KB	Output is correct
7	Correct	14 ms	8688 KB	Output is correct
8	Correct	15 ms	8688 KB	Output is correct
9	Correct	14 ms	8688 KB	Output is correct
10	Correct	13 ms	8688 KB	Output is correct
11	Correct	13 ms	8688 KB	Output is correct
12	Correct	13 ms	8688 KB	Output is correct
13	Correct	14 ms	8688 KB	Output is correct
14	Correct	14 ms	8688 KB	Output is correct
15	Correct	13 ms	8688 KB	Output is correct
16	Correct	10 ms	8688 KB	Output is correct
17	Correct	9 ms	8688 KB	Output is correct
18	Correct	9 ms	8688 KB	Output is correct
19	Correct	9 ms	8688 KB	Output is correct
20	Correct	9 ms	8688 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	8440 KB	Output is correct
2	Correct	13 ms	8440 KB	Output is correct
3	Correct	15 ms	8488 KB	Output is correct
4	Correct	14 ms	8688 KB	Output is correct
5	Correct	14 ms	8688 KB	Output is correct
6	Correct	14 ms	8688 KB	Output is correct
7	Correct	14 ms	8688 KB	Output is correct
8	Correct	15 ms	8688 KB	Output is correct
9	Correct	14 ms	8688 KB	Output is correct
10	Correct	13 ms	8688 KB	Output is correct
11	Correct	13 ms	8688 KB	Output is correct
12	Correct	13 ms	8688 KB	Output is correct
13	Correct	14 ms	8688 KB	Output is correct
14	Correct	14 ms	8688 KB	Output is correct
15	Correct	13 ms	8688 KB	Output is correct
16	Correct	10 ms	8688 KB	Output is correct
17	Correct	9 ms	8688 KB	Output is correct
18	Correct	9 ms	8688 KB	Output is correct
19	Correct	9 ms	8688 KB	Output is correct
20	Correct	9 ms	8688 KB	Output is correct
21	Incorrect	463 ms	11940 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	10 ms	11940 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	8440 KB	Output is correct
2	Correct	13 ms	8440 KB	Output is correct
3	Correct	15 ms	8488 KB	Output is correct
4	Correct	14 ms	8688 KB	Output is correct
5	Correct	14 ms	8688 KB	Output is correct
6	Correct	14 ms	8688 KB	Output is correct
7	Correct	14 ms	8688 KB	Output is correct
8	Correct	15 ms	8688 KB	Output is correct
9	Correct	14 ms	8688 KB	Output is correct
10	Correct	13 ms	8688 KB	Output is correct
11	Correct	13 ms	8688 KB	Output is correct
12	Correct	13 ms	8688 KB	Output is correct
13	Correct	14 ms	8688 KB	Output is correct
14	Correct	14 ms	8688 KB	Output is correct
15	Correct	13 ms	8688 KB	Output is correct
16	Correct	10 ms	8688 KB	Output is correct
17	Correct	9 ms	8688 KB	Output is correct
18	Correct	9 ms	8688 KB	Output is correct
19	Correct	9 ms	8688 KB	Output is correct
20	Correct	9 ms	8688 KB	Output is correct
21	Incorrect	463 ms	11940 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

답안 #40674

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
0 / 27.0

Subtask #4
0 / 42.0