답안 #52162 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52162	2018-06-24T11:20:04 Z	WLZ	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	831 ms	111716 KB

dango_maker

#include <iostream>
#include <vector>

using namespace std;

int h, w;
vector<string> s;

int solve(int y, int x) {
  vector<int> v;
  for (int k = 0; y - k >= 0 && x + k < w; k++) {
    int i = y - k;
    int j = x + k;
    if (s[i][j] != 'G') {
      v.push_back(0);
      continue;
    }
    int a = 0;
    if (j > 0 && j + 1 < w && s[i][j - 1] == 'R' && s[i][j + 1] == 'W') {
      a++;
    }
    if (i > 0 && i + 1 < h && s[i - 1][j] == 'R' && s[i + 1][j] == 'W') {
      a += 2;
    }
    v.push_back(a);
  }
  vector<vector<int>> dp((int) v.size() + 1, vector<int>(2, 0));
  for (int i = 0; i < (int) v.size(); i++) {
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 2; k++) {
        int tmp = dp[i][j];
        if ((v[i] >> k & 1) && j == k) {
          tmp++;
        }
        dp[i + 1][k] = max(dp[i + 1][k], tmp);
      }
    }
  }
  return max(dp[(int) v.size()][0], dp[(int) v.size()][1]);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> h >> w;
  s = vector<string>(h);
  for (int i = 0; i < h; i++) {
    cin >> s[i];
  }
  int ans = 0;
  for (int i = 0; i < h; i++) {
    ans += solve(i, 0);
  }
  for (int i = 1; i < w; i++) {
    ans += solve(h - 1, i);
  }
  cout << ans << '\n';
  return 0;
}

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	608 KB	Output is correct
4	Correct	2 ms	608 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	3 ms	692 KB	Output is correct
7	Correct	3 ms	808 KB	Output is correct
8	Correct	2 ms	808 KB	Output is correct
9	Correct	3 ms	808 KB	Output is correct
10	Correct	3 ms	808 KB	Output is correct
11	Correct	3 ms	808 KB	Output is correct
12	Correct	2 ms	888 KB	Output is correct
13	Correct	3 ms	900 KB	Output is correct
14	Correct	2 ms	900 KB	Output is correct
15	Correct	3 ms	900 KB	Output is correct
16	Correct	2 ms	900 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	608 KB	Output is correct
4	Correct	2 ms	608 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	3 ms	692 KB	Output is correct
7	Correct	3 ms	808 KB	Output is correct
8	Correct	2 ms	808 KB	Output is correct
9	Correct	3 ms	808 KB	Output is correct
10	Correct	3 ms	808 KB	Output is correct
11	Correct	3 ms	808 KB	Output is correct
12	Correct	2 ms	888 KB	Output is correct
13	Correct	3 ms	900 KB	Output is correct
14	Correct	2 ms	900 KB	Output is correct
15	Correct	3 ms	900 KB	Output is correct
16	Correct	2 ms	900 KB	Output is correct
17	Correct	3 ms	916 KB	Output is correct
18	Correct	2 ms	916 KB	Output is correct
19	Correct	3 ms	916 KB	Output is correct
20	Correct	2 ms	916 KB	Output is correct
21	Correct	3 ms	916 KB	Output is correct
22	Correct	2 ms	916 KB	Output is correct
23	Correct	2 ms	916 KB	Output is correct
24	Correct	3 ms	916 KB	Output is correct
25	Correct	2 ms	956 KB	Output is correct
26	Correct	2 ms	956 KB	Output is correct
27	Correct	3 ms	956 KB	Output is correct
28	Correct	3 ms	956 KB	Output is correct
29	Correct	2 ms	964 KB	Output is correct
30	Correct	2 ms	964 KB	Output is correct
31	Correct	2 ms	964 KB	Output is correct
32	Correct	3 ms	964 KB	Output is correct
33	Correct	2 ms	976 KB	Output is correct
34	Correct	2 ms	976 KB	Output is correct
35	Correct	2 ms	976 KB	Output is correct
36	Correct	2 ms	976 KB	Output is correct
37	Correct	2 ms	976 KB	Output is correct
38	Correct	3 ms	976 KB	Output is correct
39	Correct	3 ms	976 KB	Output is correct
40	Correct	2 ms	976 KB	Output is correct
41	Correct	2 ms	976 KB	Output is correct
42	Correct	2 ms	976 KB	Output is correct
43	Correct	2 ms	976 KB	Output is correct
44	Correct	2 ms	976 KB	Output is correct
45	Correct	2 ms	976 KB	Output is correct
46	Correct	3 ms	976 KB	Output is correct
47	Correct	2 ms	976 KB	Output is correct
48	Correct	2 ms	976 KB	Output is correct
49	Correct	2 ms	976 KB	Output is correct
50	Correct	3 ms	1064 KB	Output is correct
51	Correct	3 ms	1064 KB	Output is correct
52	Correct	3 ms	1064 KB	Output is correct
53	Correct	2 ms	1064 KB	Output is correct

Subtask #3
67.0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	608 KB	Output is correct
4	Correct	2 ms	608 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	3 ms	692 KB	Output is correct
7	Correct	3 ms	808 KB	Output is correct
8	Correct	2 ms	808 KB	Output is correct
9	Correct	3 ms	808 KB	Output is correct
10	Correct	3 ms	808 KB	Output is correct
11	Correct	3 ms	808 KB	Output is correct
12	Correct	2 ms	888 KB	Output is correct
13	Correct	3 ms	900 KB	Output is correct
14	Correct	2 ms	900 KB	Output is correct
15	Correct	3 ms	900 KB	Output is correct
16	Correct	2 ms	900 KB	Output is correct
17	Correct	3 ms	916 KB	Output is correct
18	Correct	2 ms	916 KB	Output is correct
19	Correct	3 ms	916 KB	Output is correct
20	Correct	2 ms	916 KB	Output is correct
21	Correct	3 ms	916 KB	Output is correct
22	Correct	2 ms	916 KB	Output is correct
23	Correct	2 ms	916 KB	Output is correct
24	Correct	3 ms	916 KB	Output is correct
25	Correct	2 ms	956 KB	Output is correct
26	Correct	2 ms	956 KB	Output is correct
27	Correct	3 ms	956 KB	Output is correct
28	Correct	3 ms	956 KB	Output is correct
29	Correct	2 ms	964 KB	Output is correct
30	Correct	2 ms	964 KB	Output is correct
31	Correct	2 ms	964 KB	Output is correct
32	Correct	3 ms	964 KB	Output is correct
33	Correct	2 ms	976 KB	Output is correct
34	Correct	2 ms	976 KB	Output is correct
35	Correct	2 ms	976 KB	Output is correct
36	Correct	2 ms	976 KB	Output is correct
37	Correct	2 ms	976 KB	Output is correct
38	Correct	3 ms	976 KB	Output is correct
39	Correct	3 ms	976 KB	Output is correct
40	Correct	2 ms	976 KB	Output is correct
41	Correct	2 ms	976 KB	Output is correct
42	Correct	2 ms	976 KB	Output is correct
43	Correct	2 ms	976 KB	Output is correct
44	Correct	2 ms	976 KB	Output is correct
45	Correct	2 ms	976 KB	Output is correct
46	Correct	3 ms	976 KB	Output is correct
47	Correct	2 ms	976 KB	Output is correct
48	Correct	2 ms	976 KB	Output is correct
49	Correct	2 ms	976 KB	Output is correct
50	Correct	3 ms	1064 KB	Output is correct
51	Correct	3 ms	1064 KB	Output is correct
52	Correct	3 ms	1064 KB	Output is correct
53	Correct	2 ms	1064 KB	Output is correct
54	Correct	4 ms	1064 KB	Output is correct
55	Correct	4 ms	1064 KB	Output is correct
56	Correct	4 ms	1064 KB	Output is correct
57	Correct	5 ms	1064 KB	Output is correct
58	Correct	127 ms	3088 KB	Output is correct
59	Correct	831 ms	20848 KB	Output is correct
60	Correct	808 ms	29700 KB	Output is correct
61	Correct	822 ms	38512 KB	Output is correct
62	Correct	4 ms	38512 KB	Output is correct
63	Correct	744 ms	46724 KB	Output is correct
64	Correct	736 ms	55832 KB	Output is correct
65	Correct	661 ms	64684 KB	Output is correct
66	Correct	787 ms	73596 KB	Output is correct
67	Correct	698 ms	82424 KB	Output is correct
68	Correct	716 ms	91168 KB	Output is correct
69	Correct	704 ms	99984 KB	Output is correct
70	Correct	73 ms	99984 KB	Output is correct
71	Correct	72 ms	99984 KB	Output is correct
72	Correct	71 ms	99984 KB	Output is correct
73	Correct	80 ms	99984 KB	Output is correct
74	Correct	84 ms	99984 KB	Output is correct
75	Correct	77 ms	99984 KB	Output is correct
76	Correct	71 ms	99984 KB	Output is correct
77	Correct	71 ms	99984 KB	Output is correct
78	Correct	72 ms	99984 KB	Output is correct
79	Correct	70 ms	100836 KB	Output is correct
80	Correct	71 ms	101816 KB	Output is correct
81	Correct	76 ms	102856 KB	Output is correct
82	Correct	71 ms	103708 KB	Output is correct
83	Correct	86 ms	104880 KB	Output is correct
84	Correct	69 ms	105728 KB	Output is correct
85	Correct	71 ms	106708 KB	Output is correct
86	Correct	69 ms	107688 KB	Output is correct
87	Correct	78 ms	108732 KB	Output is correct
88	Correct	71 ms	109648 KB	Output is correct
89	Correct	82 ms	110700 KB	Output is correct
90	Correct	74 ms	111716 KB	Output is correct

답안 #52162

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 20.0 / 20.0

Subtask #3 67.0 / 67.0

Subtask #1
13.0 / 13.0

Subtask #2
20.0 / 20.0

Subtask #3
67.0 / 67.0