oj.uz

Submission #105088

# Submission time Handle Problem Language Result Execution time Memory
105088 2019-04-10T14:06:47 Z win11905 Boat (APIO16_boat) C++11
36 / 100
 2000 ms 10320 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;
}

int f(int i, int 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 (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] * pf[z][sz-j]) % 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:43:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < coor.size()-1; ++i) 
                    ~~^~~~~~~~~~~~~~~
boat.cpp:56: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:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:38: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 1507 ms 8312 KB Output is correct
2 Correct 1523 ms 8264 KB Output is correct
3 Correct 1489 ms 8368 KB Output is correct
4 Correct 1515 ms 8476 KB Output is correct
5 Correct 1535 ms 8316 KB Output is correct
6 Correct 1514 ms 8332 KB Output is correct
7 Correct 1505 ms 8480 KB Output is correct
8 Correct 1520 ms 8368 KB Output is correct
9 Correct 1527 ms 8352 KB Output is correct
10 Correct 1515 ms 8284 KB Output is correct
11 Correct 1493 ms 8488 KB Output is correct
12 Correct 1508 ms 8320 KB Output is correct
13 Correct 1519 ms 8392 KB Output is correct
14 Correct 1556 ms 8312 KB Output is correct
15 Correct 1505 ms 8336 KB Output is correct
16 Correct 1496 ms 8408 KB Output is correct
17 Correct 1527 ms 8460 KB Output is correct
18 Correct 1509 ms 8468 KB Output is correct
19 Correct 1518 ms 8240 KB Output is correct
20 Correct 1562 ms 8276 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1507 ms 8312 KB Output is correct
2 Correct 1523 ms 8264 KB Output is correct
3 Correct 1489 ms 8368 KB Output is correct
4 Correct 1515 ms 8476 KB Output is correct
5 Correct 1535 ms 8316 KB Output is correct
6 Correct 1514 ms 8332 KB Output is correct
7 Correct 1505 ms 8480 KB Output is correct
8 Correct 1520 ms 8368 KB Output is correct
9 Correct 1527 ms 8352 KB Output is correct
10 Correct 1515 ms 8284 KB Output is correct
11 Correct 1493 ms 8488 KB Output is correct
12 Correct 1508 ms 8320 KB Output is correct
13 Correct 1519 ms 8392 KB Output is correct
14 Correct 1556 ms 8312 KB Output is correct
15 Correct 1505 ms 8336 KB Output is correct
16 Correct 1496 ms 8408 KB Output is correct
17 Correct 1527 ms 8460 KB Output is correct
18 Correct 1509 ms 8468 KB Output is correct
19 Correct 1518 ms 8240 KB Output is correct
20 Correct 1562 ms 8276 KB Output is correct
21 Execution timed out 2059 ms 10320 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1400 KB Output is correct
2 Correct 24 ms 1408 KB Output is correct
3 Correct 24 ms 1400 KB Output is correct
4 Correct 23 ms 1408 KB Output is correct
5 Correct 22 ms 1400 KB Output is correct
6 Correct 25 ms 1408 KB Output is correct
7 Correct 25 ms 1400 KB Output is correct
8 Correct 26 ms 1408 KB Output is correct
9 Correct 23 ms 1400 KB Output is correct
10 Correct 26 ms 1408 KB Output is correct
11 Correct 23 ms 1408 KB Output is correct
12 Correct 22 ms 1408 KB Output is correct
13 Correct 23 ms 1408 KB Output is correct
14 Correct 23 ms 1400 KB Output is correct
15 Correct 24 ms 1408 KB Output is correct
16 Correct 22 ms 1408 KB Output is correct
17 Correct 23 ms 1408 KB Output is correct
18 Correct 22 ms 1408 KB Output is correct
19 Correct 21 ms 1408 KB Output is correct
20 Correct 23 ms 1512 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1507 ms 8312 KB Output is correct
2 Correct 1523 ms 8264 KB Output is correct
3 Correct 1489 ms 8368 KB Output is correct
4 Correct 1515 ms 8476 KB Output is correct
5 Correct 1535 ms 8316 KB Output is correct
6 Correct 1514 ms 8332 KB Output is correct
7 Correct 1505 ms 8480 KB Output is correct
8 Correct 1520 ms 8368 KB Output is correct
9 Correct 1527 ms 8352 KB Output is correct
10 Correct 1515 ms 8284 KB Output is correct
11 Correct 1493 ms 8488 KB Output is correct
12 Correct 1508 ms 8320 KB Output is correct
13 Correct 1519 ms 8392 KB Output is correct
14 Correct 1556 ms 8312 KB Output is correct
15 Correct 1505 ms 8336 KB Output is correct
16 Correct 1496 ms 8408 KB Output is correct
17 Correct 1527 ms 8460 KB Output is correct
18 Correct 1509 ms 8468 KB Output is correct
19 Correct 1518 ms 8240 KB Output is correct
20 Correct 1562 ms 8276 KB Output is correct
21 Execution timed out 2059 ms 10320 KB Time limit exceeded
22 Halted 0 ms 0 KB -