답안 #40672 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40672	2018-02-06T17:54:15 Z	bogdan10bos	Boat (APIO16_boat)	C++14	9 / 100	1158 ms	9148 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][3005], sum[1005][3005];  /// 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;

                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	1087 ms	8696 KB	Output is correct
2	Correct	1107 ms	8752 KB	Output is correct
3	Correct	1095 ms	8792 KB	Output is correct
4	Correct	1158 ms	8792 KB	Output is correct
5	Correct	1078 ms	8948 KB	Output is correct
6	Correct	996 ms	8980 KB	Output is correct
7	Correct	977 ms	9032 KB	Output is correct
8	Correct	986 ms	9044 KB	Output is correct
9	Correct	971 ms	9044 KB	Output is correct
10	Correct	1000 ms	9084 KB	Output is correct
11	Correct	1018 ms	9084 KB	Output is correct
12	Correct	984 ms	9084 KB	Output is correct
13	Correct	1031 ms	9148 KB	Output is correct
14	Correct	980 ms	9148 KB	Output is correct
15	Correct	994 ms	9148 KB	Output is correct
16	Correct	37 ms	9148 KB	Output is correct
17	Correct	43 ms	9148 KB	Output is correct
18	Correct	46 ms	9148 KB	Output is correct
19	Correct	43 ms	9148 KB	Output is correct
20	Correct	51 ms	9148 KB	Output is correct

Subtask #2
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1087 ms	8696 KB	Output is correct
2	Correct	1107 ms	8752 KB	Output is correct
3	Correct	1095 ms	8792 KB	Output is correct
4	Correct	1158 ms	8792 KB	Output is correct
5	Correct	1078 ms	8948 KB	Output is correct
6	Correct	996 ms	8980 KB	Output is correct
7	Correct	977 ms	9032 KB	Output is correct
8	Correct	986 ms	9044 KB	Output is correct
9	Correct	971 ms	9044 KB	Output is correct
10	Correct	1000 ms	9084 KB	Output is correct
11	Correct	1018 ms	9084 KB	Output is correct
12	Correct	984 ms	9084 KB	Output is correct
13	Correct	1031 ms	9148 KB	Output is correct
14	Correct	980 ms	9148 KB	Output is correct
15	Correct	994 ms	9148 KB	Output is correct
16	Correct	37 ms	9148 KB	Output is correct
17	Correct	43 ms	9148 KB	Output is correct
18	Correct	46 ms	9148 KB	Output is correct
19	Correct	43 ms	9148 KB	Output is correct
20	Correct	51 ms	9148 KB	Output is correct
21	Runtime error	9 ms	9148 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	40 ms	9148 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1087 ms	8696 KB	Output is correct
2	Correct	1107 ms	8752 KB	Output is correct
3	Correct	1095 ms	8792 KB	Output is correct
4	Correct	1158 ms	8792 KB	Output is correct
5	Correct	1078 ms	8948 KB	Output is correct
6	Correct	996 ms	8980 KB	Output is correct
7	Correct	977 ms	9032 KB	Output is correct
8	Correct	986 ms	9044 KB	Output is correct
9	Correct	971 ms	9044 KB	Output is correct
10	Correct	1000 ms	9084 KB	Output is correct
11	Correct	1018 ms	9084 KB	Output is correct
12	Correct	984 ms	9084 KB	Output is correct
13	Correct	1031 ms	9148 KB	Output is correct
14	Correct	980 ms	9148 KB	Output is correct
15	Correct	994 ms	9148 KB	Output is correct
16	Correct	37 ms	9148 KB	Output is correct
17	Correct	43 ms	9148 KB	Output is correct
18	Correct	46 ms	9148 KB	Output is correct
19	Correct	43 ms	9148 KB	Output is correct
20	Correct	51 ms	9148 KB	Output is correct
21	Runtime error	9 ms	9148 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
22	Halted	0 ms	0 KB	-

답안 #40672

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