oj.uz

Submission #40672

# Submission time Handle Problem Language Result Execution time Memory
40672 2018-02-06T17:54:15 Z bogdan10bos Boat (APIO16_boat) C++14
9 / 100
 1158 ms 9148 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 9148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory 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 -