답안 #39794 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39794	2018-01-18T16:54:00 Z	nickyrio	Boat (APIO16_boat)	C++14	100 / 100	1883 ms	58224 KB

boat

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b ; --i)
#define REP(i, a) for (int i = 0, _a = a; i < a; ++i)
#define pp pair<int, int>
#define bit(S, i) (((S) >> i) & 1)
#define next __next
#define prev __prev
#define N 1000100
#define NN 1111
#define taskname ""
using namespace std;
 
int n, a[NN], b[NN], len[NN];
vector<int> exist;
long long rev[N];
const long long MOD = 1e9 + 7;
long long c[NN][NN], dp[NN][NN], clen[NN][NN], g[NN][NN], total[NN][NN];
 
void Add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    FOR(i, 1, n) {
        cin >> a[i] >> b[i]; b[i]++;
        exist.push_back(a[i]);
        exist.push_back(b[i]);
    }
    sort(exist.begin(), exist.end());
    exist.resize(unique(exist.begin(), exist.end()) - exist.begin());
    rev[0] = rev[1] = 1;
    FOR(i, 2, n) rev[i] = (MOD - (MOD / i) * rev[MOD % i] % MOD) % MOD;
    int sz = exist.size() - 1;
    FOR(i, 0, n) c[0][i] = 1;
    FOR(i, 1, n) {
        c[i][i] = 1;
        FOR(j, i + 1, n) c[i][j] = (c[i - 1][j - 1] + c[i][j - 1]) % MOD;
        // c[k][n]
    }
    FOR(i, 1, sz) {
        len[i] = exist[i] - exist[i - 1];
        clen[i][0] = 1;
        FOR(j, 1, n) {
            g[i][j] = 0;
            clen[i][j] = clen[i][j - 1] * (len[i] - j + 1) % MOD * rev[j] % MOD;
        }
        FOR(k, 2, n) {
            g[i][k] = 0;
            FOR(j, 2, min(k, len[i])) {
                Add(g[i][k], c[j - 2][k - 2] * clen[i][j] % MOD);
            }
        }
    }
    //
    FOR(i, 0, sz) total[0][i] = 1;
    FOR(i, 1, n) {
        FOR(j, 1, sz) {
            dp[i][j] = dp[i - 1][j];// Not choose i
 
            // Choose i
            if (a[i] <= exist[j - 1] && exist[j] <= b[i]) {
                int cnt = 0;
                FORD(k, i, 1) {
                    if (a[k] <= exist[j - 1] && exist[j] <= b[k]) {
                        cnt++;
                        if (cnt == 1) {
                            Add(dp[i][j], total[k - 1][j - 1] * 1ll * len[j] % MOD);
                        }
                        else Add(dp[i][j], total[k - 1][j - 1] * g[j][cnt] % MOD);
                    }
                }
            }
        }
        total[i][0] = 1;
        FOR(j, 1, sz) total[i][j] = (dp[i][j] + total[i][j - 1]) % MOD;
    }
    cout << (total[n][sz] - 1 + MOD) % MOD;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	660 ms	58224 KB	Output is correct
2	Correct	639 ms	58224 KB	Output is correct
3	Correct	638 ms	58224 KB	Output is correct
4	Correct	634 ms	58224 KB	Output is correct
5	Correct	648 ms	58224 KB	Output is correct
6	Correct	638 ms	58224 KB	Output is correct
7	Correct	649 ms	58224 KB	Output is correct
8	Correct	648 ms	58224 KB	Output is correct
9	Correct	640 ms	58224 KB	Output is correct
10	Correct	631 ms	58224 KB	Output is correct
11	Correct	649 ms	58224 KB	Output is correct
12	Correct	645 ms	58224 KB	Output is correct
13	Correct	646 ms	58224 KB	Output is correct
14	Correct	642 ms	58224 KB	Output is correct
15	Correct	626 ms	58224 KB	Output is correct
16	Correct	115 ms	58224 KB	Output is correct
17	Correct	121 ms	58224 KB	Output is correct
18	Correct	119 ms	58224 KB	Output is correct
19	Correct	126 ms	58224 KB	Output is correct
20	Correct	114 ms	58224 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	660 ms	58224 KB	Output is correct
2	Correct	639 ms	58224 KB	Output is correct
3	Correct	638 ms	58224 KB	Output is correct
4	Correct	634 ms	58224 KB	Output is correct
5	Correct	648 ms	58224 KB	Output is correct
6	Correct	638 ms	58224 KB	Output is correct
7	Correct	649 ms	58224 KB	Output is correct
8	Correct	648 ms	58224 KB	Output is correct
9	Correct	640 ms	58224 KB	Output is correct
10	Correct	631 ms	58224 KB	Output is correct
11	Correct	649 ms	58224 KB	Output is correct
12	Correct	645 ms	58224 KB	Output is correct
13	Correct	646 ms	58224 KB	Output is correct
14	Correct	642 ms	58224 KB	Output is correct
15	Correct	626 ms	58224 KB	Output is correct
16	Correct	115 ms	58224 KB	Output is correct
17	Correct	121 ms	58224 KB	Output is correct
18	Correct	119 ms	58224 KB	Output is correct
19	Correct	126 ms	58224 KB	Output is correct
20	Correct	114 ms	58224 KB	Output is correct
21	Correct	420 ms	58224 KB	Output is correct
22	Correct	422 ms	58224 KB	Output is correct
23	Correct	387 ms	58224 KB	Output is correct
24	Correct	414 ms	58224 KB	Output is correct
25	Correct	429 ms	58224 KB	Output is correct
26	Correct	514 ms	58224 KB	Output is correct
27	Correct	510 ms	58224 KB	Output is correct
28	Correct	576 ms	58224 KB	Output is correct
29	Correct	520 ms	58224 KB	Output is correct
30	Correct	647 ms	58224 KB	Output is correct
31	Correct	606 ms	58224 KB	Output is correct
32	Correct	608 ms	58224 KB	Output is correct
33	Correct	640 ms	58224 KB	Output is correct
34	Correct	592 ms	58224 KB	Output is correct
35	Correct	609 ms	58224 KB	Output is correct
36	Correct	608 ms	58224 KB	Output is correct
37	Correct	613 ms	58224 KB	Output is correct
38	Correct	619 ms	58224 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	58224 KB	Output is correct
2	Correct	14 ms	58224 KB	Output is correct
3	Correct	11 ms	58224 KB	Output is correct
4	Correct	12 ms	58224 KB	Output is correct
5	Correct	15 ms	58224 KB	Output is correct
6	Correct	17 ms	58224 KB	Output is correct
7	Correct	7 ms	58224 KB	Output is correct
8	Correct	17 ms	58224 KB	Output is correct
9	Correct	17 ms	58224 KB	Output is correct
10	Correct	17 ms	58224 KB	Output is correct
11	Correct	15 ms	58224 KB	Output is correct
12	Correct	3 ms	58224 KB	Output is correct
13	Correct	14 ms	58224 KB	Output is correct
14	Correct	14 ms	58224 KB	Output is correct
15	Correct	15 ms	58224 KB	Output is correct
16	Correct	5 ms	58224 KB	Output is correct
17	Correct	7 ms	58224 KB	Output is correct
18	Correct	7 ms	58224 KB	Output is correct
19	Correct	7 ms	58224 KB	Output is correct
20	Correct	3 ms	58224 KB	Output is correct

Subtask #4
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	660 ms	58224 KB	Output is correct
2	Correct	639 ms	58224 KB	Output is correct
3	Correct	638 ms	58224 KB	Output is correct
4	Correct	634 ms	58224 KB	Output is correct
5	Correct	648 ms	58224 KB	Output is correct
6	Correct	638 ms	58224 KB	Output is correct
7	Correct	649 ms	58224 KB	Output is correct
8	Correct	648 ms	58224 KB	Output is correct
9	Correct	640 ms	58224 KB	Output is correct
10	Correct	631 ms	58224 KB	Output is correct
11	Correct	649 ms	58224 KB	Output is correct
12	Correct	645 ms	58224 KB	Output is correct
13	Correct	646 ms	58224 KB	Output is correct
14	Correct	642 ms	58224 KB	Output is correct
15	Correct	626 ms	58224 KB	Output is correct
16	Correct	115 ms	58224 KB	Output is correct
17	Correct	121 ms	58224 KB	Output is correct
18	Correct	119 ms	58224 KB	Output is correct
19	Correct	126 ms	58224 KB	Output is correct
20	Correct	114 ms	58224 KB	Output is correct
21	Correct	420 ms	58224 KB	Output is correct
22	Correct	422 ms	58224 KB	Output is correct
23	Correct	387 ms	58224 KB	Output is correct
24	Correct	414 ms	58224 KB	Output is correct
25	Correct	429 ms	58224 KB	Output is correct
26	Correct	514 ms	58224 KB	Output is correct
27	Correct	510 ms	58224 KB	Output is correct
28	Correct	576 ms	58224 KB	Output is correct
29	Correct	520 ms	58224 KB	Output is correct
30	Correct	647 ms	58224 KB	Output is correct
31	Correct	606 ms	58224 KB	Output is correct
32	Correct	608 ms	58224 KB	Output is correct
33	Correct	640 ms	58224 KB	Output is correct
34	Correct	592 ms	58224 KB	Output is correct
35	Correct	609 ms	58224 KB	Output is correct
36	Correct	608 ms	58224 KB	Output is correct
37	Correct	613 ms	58224 KB	Output is correct
38	Correct	619 ms	58224 KB	Output is correct
39	Correct	10 ms	58224 KB	Output is correct
40	Correct	14 ms	58224 KB	Output is correct
41	Correct	11 ms	58224 KB	Output is correct
42	Correct	12 ms	58224 KB	Output is correct
43	Correct	15 ms	58224 KB	Output is correct
44	Correct	17 ms	58224 KB	Output is correct
45	Correct	7 ms	58224 KB	Output is correct
46	Correct	17 ms	58224 KB	Output is correct
47	Correct	17 ms	58224 KB	Output is correct
48	Correct	17 ms	58224 KB	Output is correct
49	Correct	15 ms	58224 KB	Output is correct
50	Correct	3 ms	58224 KB	Output is correct
51	Correct	14 ms	58224 KB	Output is correct
52	Correct	14 ms	58224 KB	Output is correct
53	Correct	15 ms	58224 KB	Output is correct
54	Correct	5 ms	58224 KB	Output is correct
55	Correct	7 ms	58224 KB	Output is correct
56	Correct	7 ms	58224 KB	Output is correct
57	Correct	7 ms	58224 KB	Output is correct
58	Correct	3 ms	58224 KB	Output is correct
59	Correct	1691 ms	58224 KB	Output is correct
60	Correct	1684 ms	58224 KB	Output is correct
61	Correct	1596 ms	58224 KB	Output is correct
62	Correct	1616 ms	58224 KB	Output is correct
63	Correct	1651 ms	58224 KB	Output is correct
64	Correct	1851 ms	58224 KB	Output is correct
65	Correct	1837 ms	58224 KB	Output is correct
66	Correct	1883 ms	58224 KB	Output is correct
67	Correct	1865 ms	58224 KB	Output is correct
68	Correct	1850 ms	58224 KB	Output is correct
69	Correct	1577 ms	58224 KB	Output is correct
70	Correct	1596 ms	58224 KB	Output is correct
71	Correct	1635 ms	58224 KB	Output is correct
72	Correct	1636 ms	58224 KB	Output is correct
73	Correct	1590 ms	58224 KB	Output is correct
74	Correct	202 ms	58224 KB	Output is correct
75	Correct	197 ms	58224 KB	Output is correct
76	Correct	210 ms	58224 KB	Output is correct
77	Correct	207 ms	58224 KB	Output is correct
78	Correct	205 ms	58224 KB	Output is correct

답안 #39794

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 42.0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
42.0 / 42.0