답안 #494896

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494896	2021-12-17T10:14:13 Z	XII	Boat (APIO16_boat)	C++17	100 / 100	528 ms	2456 KB

boat

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "DUT03TEAMS"
void Fi(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp", "r", stdin);
        freopen(PROB".out", "w", stdout);
    }
}

const int N = 500 + 1;
const int MOD = 1e9 + 7;
int a[N], b[N], n, m;
int dp[N][N << 1];
int X[N << 1];
int inv[N];

int add(const int &a, const int &b){
    return (a + b >= MOD ? a + b - MOD : a + b);
}

int mul(const int &a, const int &b){
    return (1LL * a * b) % MOD;
}

void compress(){
    sort(X + 1, X + m + 1);
    m = unique(X + 1, X + m + 1) - X;
    FORU(i, 1, n){
        a[i] = lower_bound(X + 1, X + m, a[i]) - X;
        b[i] = lower_bound(X + 1, X + m, b[i]) - X;
//        cout << a[i] << " " << b[i] << "\n";
    }
    m -= 2;
//    cout << m << "\n";
}

int main(){
    IOS;
    Fi();
    cin >> n;
    FORU(i, 1, n){
        cin >> a[i] >> b[i];
        X[++m] = a[i];
        X[++m] = ++b[i];
    }
    compress();

    inv[1] = 1;
    FORU(i, 2, n){
        inv[i] = mul(MOD - MOD / i, inv[MOD % i]);
    }

    int ans = 0;
    FORU(j, 0, m) dp[0][j] = 1;
    FORU(i, 1, n){
        FOR(j, a[i], b[i]){
            int len = X[j + 1] - X[j];
            int C = len, cnt = 1;
            FORD(k, i - 1, 0){
                dp[i][j] = add(dp[i][j], mul(dp[k][j - 1], C));
                if(a[k] <= j && j < b[k]){
                    ++cnt;
                    C = mul(mul(C, len + cnt - 1), inv[cnt]);
                }
            }
        }
        FORU(j, 2, m) dp[i][j] = add(dp[i][j], dp[i][j - 1]);
        ans = add(ans, dp[i][m]);
    }
    cout << ans;
    return 0;
}

Compilation message

boat.cpp: In function 'void Fi()':
boat.cpp:20:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         freopen(PROB".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen(PROB".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2252 KB	Output is correct
2	Correct	5 ms	2184 KB	Output is correct
3	Correct	4 ms	2268 KB	Output is correct
4	Correct	4 ms	2252 KB	Output is correct
5	Correct	4 ms	2252 KB	Output is correct
6	Correct	4 ms	2244 KB	Output is correct
7	Correct	4 ms	2252 KB	Output is correct
8	Correct	4 ms	2252 KB	Output is correct
9	Correct	4 ms	2252 KB	Output is correct
10	Correct	4 ms	2252 KB	Output is correct
11	Correct	4 ms	2252 KB	Output is correct
12	Correct	4 ms	2252 KB	Output is correct
13	Correct	4 ms	2252 KB	Output is correct
14	Correct	4 ms	2252 KB	Output is correct
15	Correct	4 ms	2252 KB	Output is correct
16	Correct	3 ms	2252 KB	Output is correct
17	Correct	2 ms	2252 KB	Output is correct
18	Correct	3 ms	2252 KB	Output is correct
19	Correct	3 ms	2252 KB	Output is correct
20	Correct	4 ms	2252 KB	Output is correct
21	Correct	248 ms	2272 KB	Output is correct
22	Correct	244 ms	2272 KB	Output is correct
23	Correct	223 ms	2228 KB	Output is correct
24	Correct	228 ms	2156 KB	Output is correct
25	Correct	257 ms	2208 KB	Output is correct
26	Correct	444 ms	2256 KB	Output is correct
27	Correct	461 ms	2364 KB	Output is correct
28	Correct	451 ms	2244 KB	Output is correct
29	Correct	445 ms	2220 KB	Output is correct
30	Correct	5 ms	2228 KB	Output is correct
31	Correct	5 ms	2252 KB	Output is correct
32	Correct	5 ms	2256 KB	Output is correct
33	Correct	5 ms	2248 KB	Output is correct
34	Correct	4 ms	2248 KB	Output is correct
35	Correct	6 ms	2244 KB	Output is correct
36	Correct	6 ms	2252 KB	Output is correct
37	Correct	5 ms	2256 KB	Output is correct
38	Correct	5 ms	2248 KB	Output is correct

Subtask #3
27.0 / 27.0

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

Subtask #4
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	2252 KB	Output is correct
2	Correct	5 ms	2184 KB	Output is correct
3	Correct	4 ms	2268 KB	Output is correct
4	Correct	4 ms	2252 KB	Output is correct
5	Correct	4 ms	2252 KB	Output is correct
6	Correct	4 ms	2244 KB	Output is correct
7	Correct	4 ms	2252 KB	Output is correct
8	Correct	4 ms	2252 KB	Output is correct
9	Correct	4 ms	2252 KB	Output is correct
10	Correct	4 ms	2252 KB	Output is correct
11	Correct	4 ms	2252 KB	Output is correct
12	Correct	4 ms	2252 KB	Output is correct
13	Correct	4 ms	2252 KB	Output is correct
14	Correct	4 ms	2252 KB	Output is correct
15	Correct	4 ms	2252 KB	Output is correct
16	Correct	3 ms	2252 KB	Output is correct
17	Correct	2 ms	2252 KB	Output is correct
18	Correct	3 ms	2252 KB	Output is correct
19	Correct	3 ms	2252 KB	Output is correct
20	Correct	4 ms	2252 KB	Output is correct
21	Correct	248 ms	2272 KB	Output is correct
22	Correct	244 ms	2272 KB	Output is correct
23	Correct	223 ms	2228 KB	Output is correct
24	Correct	228 ms	2156 KB	Output is correct
25	Correct	257 ms	2208 KB	Output is correct
26	Correct	444 ms	2256 KB	Output is correct
27	Correct	461 ms	2364 KB	Output is correct
28	Correct	451 ms	2244 KB	Output is correct
29	Correct	445 ms	2220 KB	Output is correct
30	Correct	5 ms	2228 KB	Output is correct
31	Correct	5 ms	2252 KB	Output is correct
32	Correct	5 ms	2256 KB	Output is correct
33	Correct	5 ms	2248 KB	Output is correct
34	Correct	4 ms	2248 KB	Output is correct
35	Correct	6 ms	2244 KB	Output is correct
36	Correct	6 ms	2252 KB	Output is correct
37	Correct	5 ms	2256 KB	Output is correct
38	Correct	5 ms	2248 KB	Output is correct
39	Correct	3 ms	716 KB	Output is correct
40	Correct	2 ms	720 KB	Output is correct
41	Correct	3 ms	832 KB	Output is correct
42	Correct	3 ms	708 KB	Output is correct
43	Correct	3 ms	720 KB	Output is correct
44	Correct	5 ms	720 KB	Output is correct
45	Correct	4 ms	708 KB	Output is correct
46	Correct	5 ms	716 KB	Output is correct
47	Correct	5 ms	720 KB	Output is correct
48	Correct	5 ms	720 KB	Output is correct
49	Correct	3 ms	720 KB	Output is correct
50	Correct	2 ms	720 KB	Output is correct
51	Correct	3 ms	640 KB	Output is correct
52	Correct	3 ms	720 KB	Output is correct
53	Correct	3 ms	636 KB	Output is correct
54	Correct	2 ms	720 KB	Output is correct
55	Correct	2 ms	720 KB	Output is correct
56	Correct	2 ms	720 KB	Output is correct
57	Correct	2 ms	720 KB	Output is correct
58	Correct	3 ms	720 KB	Output is correct
59	Correct	271 ms	2264 KB	Output is correct
60	Correct	251 ms	2244 KB	Output is correct
61	Correct	230 ms	2304 KB	Output is correct
62	Correct	263 ms	2240 KB	Output is correct
63	Correct	250 ms	2192 KB	Output is correct
64	Correct	517 ms	2332 KB	Output is correct
65	Correct	519 ms	2168 KB	Output is correct
66	Correct	520 ms	2304 KB	Output is correct
67	Correct	528 ms	2456 KB	Output is correct
68	Correct	513 ms	2356 KB	Output is correct
69	Correct	222 ms	2388 KB	Output is correct
70	Correct	212 ms	2176 KB	Output is correct
71	Correct	210 ms	2372 KB	Output is correct
72	Correct	228 ms	2228 KB	Output is correct
73	Correct	224 ms	2288 KB	Output is correct
74	Correct	55 ms	2160 KB	Output is correct
75	Correct	51 ms	2248 KB	Output is correct
76	Correct	56 ms	2232 KB	Output is correct
77	Correct	56 ms	2248 KB	Output is correct
78	Correct	55 ms	2244 KB	Output is correct

답안 #494896

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