답안 #40673 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40673	2018-02-06T17:57:49 Z	bogdan10bos	Boat (APIO16_boat)	C++14	9 / 100	19 ms	8708 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 = j; 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	14 ms	8440 KB	Output is correct
2	Correct	16 ms	8516 KB	Output is correct
3	Correct	14 ms	8588 KB	Output is correct
4	Correct	14 ms	8588 KB	Output is correct
5	Correct	15 ms	8636 KB	Output is correct
6	Correct	13 ms	8708 KB	Output is correct
7	Correct	14 ms	8708 KB	Output is correct
8	Correct	15 ms	8708 KB	Output is correct
9	Correct	14 ms	8708 KB	Output is correct
10	Correct	13 ms	8708 KB	Output is correct
11	Correct	14 ms	8708 KB	Output is correct
12	Correct	16 ms	8708 KB	Output is correct
13	Correct	13 ms	8708 KB	Output is correct
14	Correct	14 ms	8708 KB	Output is correct
15	Correct	14 ms	8708 KB	Output is correct
16	Correct	9 ms	8708 KB	Output is correct
17	Correct	10 ms	8708 KB	Output is correct
18	Correct	9 ms	8708 KB	Output is correct
19	Correct	10 ms	8708 KB	Output is correct
20	Correct	9 ms	8708 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	8440 KB	Output is correct
2	Correct	16 ms	8516 KB	Output is correct
3	Correct	14 ms	8588 KB	Output is correct
4	Correct	14 ms	8588 KB	Output is correct
5	Correct	15 ms	8636 KB	Output is correct
6	Correct	13 ms	8708 KB	Output is correct
7	Correct	14 ms	8708 KB	Output is correct
8	Correct	15 ms	8708 KB	Output is correct
9	Correct	14 ms	8708 KB	Output is correct
10	Correct	13 ms	8708 KB	Output is correct
11	Correct	14 ms	8708 KB	Output is correct
12	Correct	16 ms	8708 KB	Output is correct
13	Correct	13 ms	8708 KB	Output is correct
14	Correct	14 ms	8708 KB	Output is correct
15	Correct	14 ms	8708 KB	Output is correct
16	Correct	9 ms	8708 KB	Output is correct
17	Correct	10 ms	8708 KB	Output is correct
18	Correct	9 ms	8708 KB	Output is correct
19	Correct	10 ms	8708 KB	Output is correct
20	Correct	9 ms	8708 KB	Output is correct
21	Runtime error	8 ms	8708 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Halted	0 ms	0 KB	-

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	14 ms	8440 KB	Output is correct
2	Correct	16 ms	8516 KB	Output is correct
3	Correct	14 ms	8588 KB	Output is correct
4	Correct	14 ms	8588 KB	Output is correct
5	Correct	15 ms	8636 KB	Output is correct
6	Correct	13 ms	8708 KB	Output is correct
7	Correct	14 ms	8708 KB	Output is correct
8	Correct	15 ms	8708 KB	Output is correct
9	Correct	14 ms	8708 KB	Output is correct
10	Correct	13 ms	8708 KB	Output is correct
11	Correct	14 ms	8708 KB	Output is correct
12	Correct	16 ms	8708 KB	Output is correct
13	Correct	13 ms	8708 KB	Output is correct
14	Correct	14 ms	8708 KB	Output is correct
15	Correct	14 ms	8708 KB	Output is correct
16	Correct	9 ms	8708 KB	Output is correct
17	Correct	10 ms	8708 KB	Output is correct
18	Correct	9 ms	8708 KB	Output is correct
19	Correct	10 ms	8708 KB	Output is correct
20	Correct	9 ms	8708 KB	Output is correct
21	Runtime error	8 ms	8708 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Halted	0 ms	0 KB	-

답안 #40673

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