답안 #68134 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
68134	2018-08-16T05:39:38 Z	funcsr	Boat (APIO16_boat)	C++17	100 / 100	1201 ms	5556 KB

boat

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
inline void add(int &x, int v) { x += v; if (x >= MOD) x -= MOD; }
inline int mul(int x, int y) { return (1LL*x*y)%MOD; }
int modpow(int x, int k) {
  int a = 1;
  while (k) {
    if (k&1) a = mul(a, x);
    x = mul(x, x);
    k >>= 1;
  }
  return a;
}

int N;
int A[500], B[500];
int inv[501];
int dp[2][1000][501];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  rep(k, N+1) inv[k] = modpow(k, MOD-2);
  vector<int> ys;
  rep(i, N) cin >> A[i] >> B[i], ys.pb(A[i]), ys.pb(B[i]+1);
  sort(all(ys)); uniq(ys);
  rep(i, N) A[i] = index(ys, A[i]), B[i] = index(ys, B[i]+1)-1;

  dp[0][0][0] = 1;
  rep(i, N) {
    rep(j, ys.size()-1) rep(k, i+2) dp[1][j][k] = dp[0][j][k];
    for (int j=A[i]; j<=B[i]; j++) rep(k, i+1) add(dp[1][j][k+1], mul(dp[0][j][k], mul(ys[j+1]-ys[j]-k, inv[k+1])));
    int s = 0;
    rep(t, B[i]+1) {
      if (t >= A[i]) add(dp[1][t][1], mul(ys[t+1]-ys[t], s));
      rep(k, i+1) add(s, dp[0][t][k]);
    }
    swap(dp[0], dp[1]);
  }
  int s = MOD-1;
  rep(j, ys.size()-1) rep(k, N+1) add(s, dp[0][j][k]);
  cout << s << "\n";
  return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:17:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
boat.cpp:54:5: note: in expansion of macro 'rep'
     rep(j, ys.size()-1) rep(k, i+2) dp[1][j][k] = dp[0][j][k];
     ^~~
boat.cpp:17:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
boat.cpp:64:3: note: in expansion of macro 'rep'
   rep(j, ys.size()-1) rep(k, N+1) add(s, dp[0][j][k]);
   ^~~

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	526 ms	4404 KB	Output is correct
2	Correct	530 ms	4456 KB	Output is correct
3	Correct	583 ms	4588 KB	Output is correct
4	Correct	496 ms	4632 KB	Output is correct
5	Correct	472 ms	4632 KB	Output is correct
6	Correct	591 ms	4800 KB	Output is correct
7	Correct	574 ms	4800 KB	Output is correct
8	Correct	519 ms	4888 KB	Output is correct
9	Correct	498 ms	4888 KB	Output is correct
10	Correct	522 ms	4888 KB	Output is correct
11	Correct	530 ms	4888 KB	Output is correct
12	Correct	476 ms	4888 KB	Output is correct
13	Correct	563 ms	4888 KB	Output is correct
14	Correct	529 ms	4888 KB	Output is correct
15	Correct	488 ms	4920 KB	Output is correct
16	Correct	311 ms	4928 KB	Output is correct
17	Correct	346 ms	4968 KB	Output is correct
18	Correct	324 ms	4972 KB	Output is correct
19	Correct	312 ms	4972 KB	Output is correct
20	Correct	338 ms	4976 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	526 ms	4404 KB	Output is correct
2	Correct	530 ms	4456 KB	Output is correct
3	Correct	583 ms	4588 KB	Output is correct
4	Correct	496 ms	4632 KB	Output is correct
5	Correct	472 ms	4632 KB	Output is correct
6	Correct	591 ms	4800 KB	Output is correct
7	Correct	574 ms	4800 KB	Output is correct
8	Correct	519 ms	4888 KB	Output is correct
9	Correct	498 ms	4888 KB	Output is correct
10	Correct	522 ms	4888 KB	Output is correct
11	Correct	530 ms	4888 KB	Output is correct
12	Correct	476 ms	4888 KB	Output is correct
13	Correct	563 ms	4888 KB	Output is correct
14	Correct	529 ms	4888 KB	Output is correct
15	Correct	488 ms	4920 KB	Output is correct
16	Correct	311 ms	4928 KB	Output is correct
17	Correct	346 ms	4968 KB	Output is correct
18	Correct	324 ms	4972 KB	Output is correct
19	Correct	312 ms	4972 KB	Output is correct
20	Correct	338 ms	4976 KB	Output is correct
21	Correct	897 ms	4976 KB	Output is correct
22	Correct	777 ms	4976 KB	Output is correct
23	Correct	824 ms	5128 KB	Output is correct
24	Correct	864 ms	5128 KB	Output is correct
25	Correct	798 ms	5128 KB	Output is correct
26	Correct	917 ms	5128 KB	Output is correct
27	Correct	881 ms	5128 KB	Output is correct
28	Correct	901 ms	5128 KB	Output is correct
29	Correct	899 ms	5128 KB	Output is correct
30	Correct	532 ms	5128 KB	Output is correct
31	Correct	640 ms	5128 KB	Output is correct
32	Correct	617 ms	5128 KB	Output is correct
33	Correct	547 ms	5128 KB	Output is correct
34	Correct	555 ms	5128 KB	Output is correct
35	Correct	515 ms	5148 KB	Output is correct
36	Correct	526 ms	5148 KB	Output is correct
37	Correct	506 ms	5148 KB	Output is correct
38	Correct	516 ms	5148 KB	Output is correct

Subtask #3
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	69 ms	5148 KB	Output is correct
2	Correct	86 ms	5148 KB	Output is correct
3	Correct	82 ms	5148 KB	Output is correct
4	Correct	75 ms	5200 KB	Output is correct
5	Correct	66 ms	5200 KB	Output is correct
6	Correct	93 ms	5200 KB	Output is correct
7	Correct	80 ms	5200 KB	Output is correct
8	Correct	91 ms	5200 KB	Output is correct
9	Correct	79 ms	5200 KB	Output is correct
10	Correct	68 ms	5200 KB	Output is correct
11	Correct	73 ms	5228 KB	Output is correct
12	Correct	65 ms	5228 KB	Output is correct
13	Correct	69 ms	5228 KB	Output is correct
14	Correct	73 ms	5228 KB	Output is correct
15	Correct	67 ms	5228 KB	Output is correct
16	Correct	83 ms	5228 KB	Output is correct
17	Correct	71 ms	5228 KB	Output is correct
18	Correct	78 ms	5256 KB	Output is correct
19	Correct	78 ms	5256 KB	Output is correct
20	Correct	66 ms	5256 KB	Output is correct

Subtask #4
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	526 ms	4404 KB	Output is correct
2	Correct	530 ms	4456 KB	Output is correct
3	Correct	583 ms	4588 KB	Output is correct
4	Correct	496 ms	4632 KB	Output is correct
5	Correct	472 ms	4632 KB	Output is correct
6	Correct	591 ms	4800 KB	Output is correct
7	Correct	574 ms	4800 KB	Output is correct
8	Correct	519 ms	4888 KB	Output is correct
9	Correct	498 ms	4888 KB	Output is correct
10	Correct	522 ms	4888 KB	Output is correct
11	Correct	530 ms	4888 KB	Output is correct
12	Correct	476 ms	4888 KB	Output is correct
13	Correct	563 ms	4888 KB	Output is correct
14	Correct	529 ms	4888 KB	Output is correct
15	Correct	488 ms	4920 KB	Output is correct
16	Correct	311 ms	4928 KB	Output is correct
17	Correct	346 ms	4968 KB	Output is correct
18	Correct	324 ms	4972 KB	Output is correct
19	Correct	312 ms	4972 KB	Output is correct
20	Correct	338 ms	4976 KB	Output is correct
21	Correct	897 ms	4976 KB	Output is correct
22	Correct	777 ms	4976 KB	Output is correct
23	Correct	824 ms	5128 KB	Output is correct
24	Correct	864 ms	5128 KB	Output is correct
25	Correct	798 ms	5128 KB	Output is correct
26	Correct	917 ms	5128 KB	Output is correct
27	Correct	881 ms	5128 KB	Output is correct
28	Correct	901 ms	5128 KB	Output is correct
29	Correct	899 ms	5128 KB	Output is correct
30	Correct	532 ms	5128 KB	Output is correct
31	Correct	640 ms	5128 KB	Output is correct
32	Correct	617 ms	5128 KB	Output is correct
33	Correct	547 ms	5128 KB	Output is correct
34	Correct	555 ms	5128 KB	Output is correct
35	Correct	515 ms	5148 KB	Output is correct
36	Correct	526 ms	5148 KB	Output is correct
37	Correct	506 ms	5148 KB	Output is correct
38	Correct	516 ms	5148 KB	Output is correct
39	Correct	69 ms	5148 KB	Output is correct
40	Correct	86 ms	5148 KB	Output is correct
41	Correct	82 ms	5148 KB	Output is correct
42	Correct	75 ms	5200 KB	Output is correct
43	Correct	66 ms	5200 KB	Output is correct
44	Correct	93 ms	5200 KB	Output is correct
45	Correct	80 ms	5200 KB	Output is correct
46	Correct	91 ms	5200 KB	Output is correct
47	Correct	79 ms	5200 KB	Output is correct
48	Correct	68 ms	5200 KB	Output is correct
49	Correct	73 ms	5228 KB	Output is correct
50	Correct	65 ms	5228 KB	Output is correct
51	Correct	69 ms	5228 KB	Output is correct
52	Correct	73 ms	5228 KB	Output is correct
53	Correct	67 ms	5228 KB	Output is correct
54	Correct	83 ms	5228 KB	Output is correct
55	Correct	71 ms	5228 KB	Output is correct
56	Correct	78 ms	5256 KB	Output is correct
57	Correct	78 ms	5256 KB	Output is correct
58	Correct	66 ms	5256 KB	Output is correct
59	Correct	799 ms	5256 KB	Output is correct
60	Correct	789 ms	5256 KB	Output is correct
61	Correct	790 ms	5296 KB	Output is correct
62	Correct	779 ms	5436 KB	Output is correct
63	Correct	821 ms	5436 KB	Output is correct
64	Correct	974 ms	5436 KB	Output is correct
65	Correct	1084 ms	5436 KB	Output is correct
66	Correct	1052 ms	5436 KB	Output is correct
67	Correct	1058 ms	5436 KB	Output is correct
68	Correct	1201 ms	5436 KB	Output is correct
69	Correct	886 ms	5436 KB	Output is correct
70	Correct	796 ms	5436 KB	Output is correct
71	Correct	763 ms	5436 KB	Output is correct
72	Correct	784 ms	5436 KB	Output is correct
73	Correct	720 ms	5556 KB	Output is correct
74	Correct	397 ms	5556 KB	Output is correct
75	Correct	401 ms	5556 KB	Output is correct
76	Correct	444 ms	5556 KB	Output is correct
77	Correct	440 ms	5556 KB	Output is correct
78	Correct	426 ms	5556 KB	Output is correct

답안 #68134

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