oj.uz

Submission #105090

# Submission time Handle Problem Language Result Execution time Memory
105090 2019-04-10T14:17:24 Z win11905 Boat (APIO16_boat) C++11
36 / 100
 2000 ms 2080 KB 
#include <bits/stdc++.h>
#define long long long
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int N = 1e3+5;
const int M = 1e9+7;

int n;
long dp[N], pf[N][N];
vector<long> vec[N];
vector<pii> que;
vector<int> coor;

int powMod(int a, int b) {
    int val = 1;
    for(; b; b >>= 1) {
        if(b & 1) val = (1ll * val * a) % M;
        a = (1ll * a * a) % M;
    } 
    return val;
}

struct coorh {
    size_t operator()(const pii &z) const {
        return z.x + z.y;
    }
};

unordered_map<pii, int, coorh> Mp;

int f(int i, int x) {
    if(Mp.count(pii(i, x))) return Mp[pii(i, x)];
    int up = 1, down = 1;
    for(int j = x; j < i+x; ++j) up = (1ll * up * j) % M;
    for(int j = 1; j <= i; ++j) down = (1ll * down * j) % M;
    return Mp[pii(i, x)] = (1ll * up * powMod(down, M-2)) % M;
}

int main() {
    scanf("%d", &n);
    dp[0] = 1, coor.emplace_back(0);
    for(int i = 0, a, b; i < n; ++i) {
        scanf("%d %d", &a, &b), b++;
        coor.emplace_back(a), coor.emplace_back(b);
        que.emplace_back(a, b);
    }
    sort(all(coor));
    // for(int i = 1; i < coor.size()-1; ++i) 
    //     for(int j = 1; j <= n; ++j) pf[i][j] = f(j, coor[i+1] - coor[i]);
    for(int i = 0, l, r; i < n; ++i) {
        tie(l, r) = que[i];
        l = lower_bound(all(coor), l) - coor.begin(), r = lower_bound(all(coor), r) - coor.begin();
        for(int z = r-1, sum = 0; z >= l; --z, sum = 0) {
            for(int k = z-1; ~k; --k) sum = (sum + dp[k]) % M;
            vec[z].emplace_back(sum), dp[z] = 0;
            int sz = vec[z].size();
            for(int j = 0; j < sz; ++j) dp[z] = (dp[z] + 1ll * vec[z][j] * f(sz-j, coor[z+1] - coor[z])) % M;
        }
    } 
    int ans = 0;
    for(int i = 1; i < coor.size()-1; ++i) ans = (ans + dp[i]) % M;
    printf("%d\n", ans);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < coor.size()-1; ++i) ans = (ans + dp[i]) % M;
                    ~~^~~~~~~~~~~~~~~
boat.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:47:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b), b++;
         ~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 13 ms 384 KB Output is correct
17 Correct 14 ms 384 KB Output is correct
18 Correct 9 ms 384 KB Output is correct
19 Correct 12 ms 384 KB Output is correct
20 Correct 13 ms 384 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 13 ms 384 KB Output is correct
17 Correct 14 ms 384 KB Output is correct
18 Correct 9 ms 384 KB Output is correct
19 Correct 12 ms 384 KB Output is correct
20 Correct 13 ms 384 KB Output is correct
21 Execution timed out 2044 ms 2080 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 896 KB Output is correct
2 Correct 14 ms 768 KB Output is correct
3 Correct 19 ms 768 KB Output is correct
4 Correct 21 ms 896 KB Output is correct
5 Correct 29 ms 888 KB Output is correct
6 Correct 38 ms 1016 KB Output is correct
7 Correct 39 ms 1016 KB Output is correct
8 Correct 37 ms 1024 KB Output is correct
9 Correct 39 ms 1016 KB Output is correct
10 Correct 41 ms 1016 KB Output is correct
11 Correct 22 ms 864 KB Output is correct
12 Correct 16 ms 768 KB Output is correct
13 Correct 19 ms 896 KB Output is correct
14 Correct 17 ms 768 KB Output is correct
15 Correct 21 ms 888 KB Output is correct
16 Correct 18 ms 640 KB Output is correct
17 Correct 15 ms 588 KB Output is correct
18 Correct 16 ms 640 KB Output is correct
19 Correct 15 ms 512 KB Output is correct
20 Correct 21 ms 608 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 13 ms 384 KB Output is correct
17 Correct 14 ms 384 KB Output is correct
18 Correct 9 ms 384 KB Output is correct
19 Correct 12 ms 384 KB Output is correct
20 Correct 13 ms 384 KB Output is correct
21 Execution timed out 2044 ms 2080 KB Time limit exceeded
22 Halted 0 ms 0 KB -