답안 #849157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
849157	2023-09-14T07:38:37 Z	tch1cherin	Boat (APIO16_boat)	C++17	100 / 100	1822 ms	7156 KB

boat

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int inverse(int x) {
  int base = x, power = MOD - 2;
  int result = 1;
  while (power > 0) {
    if (power & 1) {
      result = 1LL * result * base % MOD;
    }
    base = 1LL * base * base % MOD;
    power /= 2;
  }
  return result;
}
 
void norm(int& X) {
  X -= X >= MOD ? MOD : 0;
}
 
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> A(N), B(N);
  vector<int> points;
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
    points.push_back(A[i]);
    points.push_back(B[i] + 1);
  }
  sort(points.begin(), points.end());
  points.resize(unique(points.begin(), points.end()) - points.begin());
  vector<int> new_points;
  for (int i = 0; i < (int)points.size(); i++) {
    new_points.push_back(points[i]);
    /*if (i + 1 < (int)points.size() && points[i + 1] - points[i] > 1) {
      new_points.push_back(points[i] + 1);
    }*/
  }
  points = new_points;
  int M = (int)points.size();
  vector<int> weight(M);
  vector<vector<int>> choose_weight(M, vector<int>(N + 1));
  for (int i = 0; i < M; i++) {
    weight[i] = (i == M - 1 ? 1 : points[i + 1] - points[i]);
    choose_weight[i][0] = 1;
    for (int j = 0; j < weight[i] && j < N; j++) {
      int coefficient = 1LL * (weight[i] - j) * inverse(j + 1) % MOD;  
      choose_weight[i][j + 1] = 1LL * choose_weight[i][j] * coefficient % MOD;
    }
  }
  vector<vector<int>> ways(M, vector<int>(N + 1));
  vector<int> pref(M + 1);
  for (int i = 0; i < M; i++) {
    ways[i][0] = 1;
  }
  for (int i = 0; i < N; i++) {
    vector<vector<int>> new_ways(M, vector<int>(N + 1));
    for (int j = 0; j < M; j++) {
      if (A[i] <= points[j] && points[j] <= B[i]) {
        new_ways[j][1] += pref[j];
      }
      for (int k = 0; k < N; k++) {
        norm(new_ways[j][k] += ways[j][k]);
        if (A[i] <= points[j] && points[j] <= B[i]) {
          norm(new_ways[j][k + 1] += ways[j][k]);
        }
      }
    }
    for (int j = 0; j < M; j++) {
      pref[j + 1] = pref[j];
      for (int k = 1; k <= N && k <= weight[j]; k++) {
        pref[j + 1] = (pref[j + 1] + 1LL * new_ways[j][k] * choose_weight[j][k]) % MOD;
      }
    }
    ways = new_ways;
  }
  cout << pref[M] << "\n";
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1173 ms	6844 KB	Output is correct
2	Correct	1180 ms	6816 KB	Output is correct
3	Correct	1179 ms	6656 KB	Output is correct
4	Correct	1189 ms	6516 KB	Output is correct
5	Correct	1188 ms	6736 KB	Output is correct
6	Correct	1138 ms	6540 KB	Output is correct
7	Correct	1134 ms	6896 KB	Output is correct
8	Correct	1189 ms	6792 KB	Output is correct
9	Correct	1156 ms	6556 KB	Output is correct
10	Correct	1144 ms	6756 KB	Output is correct
11	Correct	1144 ms	6908 KB	Output is correct
12	Correct	1178 ms	6536 KB	Output is correct
13	Correct	1157 ms	6972 KB	Output is correct
14	Correct	1176 ms	6800 KB	Output is correct
15	Correct	1153 ms	6764 KB	Output is correct
16	Correct	193 ms	1496 KB	Output is correct
17	Correct	223 ms	2200 KB	Output is correct
18	Correct	208 ms	1728 KB	Output is correct
19	Correct	216 ms	2140 KB	Output is correct
20	Correct	210 ms	1624 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1173 ms	6844 KB	Output is correct
2	Correct	1180 ms	6816 KB	Output is correct
3	Correct	1179 ms	6656 KB	Output is correct
4	Correct	1189 ms	6516 KB	Output is correct
5	Correct	1188 ms	6736 KB	Output is correct
6	Correct	1138 ms	6540 KB	Output is correct
7	Correct	1134 ms	6896 KB	Output is correct
8	Correct	1189 ms	6792 KB	Output is correct
9	Correct	1156 ms	6556 KB	Output is correct
10	Correct	1144 ms	6756 KB	Output is correct
11	Correct	1144 ms	6908 KB	Output is correct
12	Correct	1178 ms	6536 KB	Output is correct
13	Correct	1157 ms	6972 KB	Output is correct
14	Correct	1176 ms	6800 KB	Output is correct
15	Correct	1153 ms	6764 KB	Output is correct
16	Correct	193 ms	1496 KB	Output is correct
17	Correct	223 ms	2200 KB	Output is correct
18	Correct	208 ms	1728 KB	Output is correct
19	Correct	216 ms	2140 KB	Output is correct
20	Correct	210 ms	1624 KB	Output is correct
21	Correct	615 ms	6024 KB	Output is correct
22	Correct	627 ms	6332 KB	Output is correct
23	Correct	628 ms	6260 KB	Output is correct
24	Correct	631 ms	6048 KB	Output is correct
25	Correct	638 ms	5884 KB	Output is correct
26	Correct	628 ms	5860 KB	Output is correct
27	Correct	688 ms	6044 KB	Output is correct
28	Correct	638 ms	6380 KB	Output is correct
29	Correct	634 ms	5916 KB	Output is correct
30	Correct	1111 ms	6496 KB	Output is correct
31	Correct	1128 ms	6920 KB	Output is correct
32	Correct	1119 ms	6640 KB	Output is correct
33	Correct	1139 ms	6604 KB	Output is correct
34	Correct	1100 ms	6868 KB	Output is correct
35	Correct	1132 ms	6592 KB	Output is correct
36	Correct	1130 ms	6796 KB	Output is correct
37	Correct	1110 ms	6672 KB	Output is correct
38	Correct	1139 ms	6752 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	604 KB	Output is correct
2	Correct	15 ms	716 KB	Output is correct
3	Correct	15 ms	604 KB	Output is correct
4	Correct	15 ms	720 KB	Output is correct
5	Correct	15 ms	604 KB	Output is correct
6	Correct	15 ms	604 KB	Output is correct
7	Correct	16 ms	604 KB	Output is correct
8	Correct	16 ms	800 KB	Output is correct
9	Correct	17 ms	604 KB	Output is correct
10	Correct	17 ms	604 KB	Output is correct
11	Correct	15 ms	720 KB	Output is correct
12	Correct	15 ms	712 KB	Output is correct
13	Correct	15 ms	604 KB	Output is correct
14	Correct	15 ms	544 KB	Output is correct
15	Correct	16 ms	716 KB	Output is correct
16	Correct	8 ms	344 KB	Output is correct
17	Correct	8 ms	348 KB	Output is correct
18	Correct	8 ms	348 KB	Output is correct
19	Correct	7 ms	600 KB	Output is correct
20	Correct	8 ms	608 KB	Output is correct

Subtask #4
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1173 ms	6844 KB	Output is correct
2	Correct	1180 ms	6816 KB	Output is correct
3	Correct	1179 ms	6656 KB	Output is correct
4	Correct	1189 ms	6516 KB	Output is correct
5	Correct	1188 ms	6736 KB	Output is correct
6	Correct	1138 ms	6540 KB	Output is correct
7	Correct	1134 ms	6896 KB	Output is correct
8	Correct	1189 ms	6792 KB	Output is correct
9	Correct	1156 ms	6556 KB	Output is correct
10	Correct	1144 ms	6756 KB	Output is correct
11	Correct	1144 ms	6908 KB	Output is correct
12	Correct	1178 ms	6536 KB	Output is correct
13	Correct	1157 ms	6972 KB	Output is correct
14	Correct	1176 ms	6800 KB	Output is correct
15	Correct	1153 ms	6764 KB	Output is correct
16	Correct	193 ms	1496 KB	Output is correct
17	Correct	223 ms	2200 KB	Output is correct
18	Correct	208 ms	1728 KB	Output is correct
19	Correct	216 ms	2140 KB	Output is correct
20	Correct	210 ms	1624 KB	Output is correct
21	Correct	615 ms	6024 KB	Output is correct
22	Correct	627 ms	6332 KB	Output is correct
23	Correct	628 ms	6260 KB	Output is correct
24	Correct	631 ms	6048 KB	Output is correct
25	Correct	638 ms	5884 KB	Output is correct
26	Correct	628 ms	5860 KB	Output is correct
27	Correct	688 ms	6044 KB	Output is correct
28	Correct	638 ms	6380 KB	Output is correct
29	Correct	634 ms	5916 KB	Output is correct
30	Correct	1111 ms	6496 KB	Output is correct
31	Correct	1128 ms	6920 KB	Output is correct
32	Correct	1119 ms	6640 KB	Output is correct
33	Correct	1139 ms	6604 KB	Output is correct
34	Correct	1100 ms	6868 KB	Output is correct
35	Correct	1132 ms	6592 KB	Output is correct
36	Correct	1130 ms	6796 KB	Output is correct
37	Correct	1110 ms	6672 KB	Output is correct
38	Correct	1139 ms	6752 KB	Output is correct
39	Correct	15 ms	604 KB	Output is correct
40	Correct	15 ms	716 KB	Output is correct
41	Correct	15 ms	604 KB	Output is correct
42	Correct	15 ms	720 KB	Output is correct
43	Correct	15 ms	604 KB	Output is correct
44	Correct	15 ms	604 KB	Output is correct
45	Correct	16 ms	604 KB	Output is correct
46	Correct	16 ms	800 KB	Output is correct
47	Correct	17 ms	604 KB	Output is correct
48	Correct	17 ms	604 KB	Output is correct
49	Correct	15 ms	720 KB	Output is correct
50	Correct	15 ms	712 KB	Output is correct
51	Correct	15 ms	604 KB	Output is correct
52	Correct	15 ms	544 KB	Output is correct
53	Correct	16 ms	716 KB	Output is correct
54	Correct	8 ms	344 KB	Output is correct
55	Correct	8 ms	348 KB	Output is correct
56	Correct	8 ms	348 KB	Output is correct
57	Correct	7 ms	600 KB	Output is correct
58	Correct	8 ms	608 KB	Output is correct
59	Correct	1787 ms	7156 KB	Output is correct
60	Correct	1781 ms	6896 KB	Output is correct
61	Correct	1774 ms	6596 KB	Output is correct
62	Correct	1796 ms	6900 KB	Output is correct
63	Correct	1794 ms	7016 KB	Output is correct
64	Correct	1814 ms	6688 KB	Output is correct
65	Correct	1802 ms	6884 KB	Output is correct
66	Correct	1798 ms	6744 KB	Output is correct
67	Correct	1822 ms	6732 KB	Output is correct
68	Correct	1777 ms	6608 KB	Output is correct
69	Correct	1763 ms	7016 KB	Output is correct
70	Correct	1757 ms	6864 KB	Output is correct
71	Correct	1763 ms	6900 KB	Output is correct
72	Correct	1764 ms	6656 KB	Output is correct
73	Correct	1751 ms	6888 KB	Output is correct
74	Correct	230 ms	1724 KB	Output is correct
75	Correct	240 ms	1580 KB	Output is correct
76	Correct	220 ms	1824 KB	Output is correct
77	Correct	228 ms	1720 KB	Output is correct
78	Correct	221 ms	1560 KB	Output is correct

답안 #849157

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