답안 #74597 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74597	2018-09-05T00:59:09 Z	garyye	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	515 ms	113288 KB

dango_maker

// author: gary
// created: 2018/09/04 09:19:17
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <limits>
#include <utility>
#include <functional>
#include <string>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
#define SZ(x) ( (int) (x).size() )
#define ALL(c) (c).begin(), (c).end()
#define CNT(c, x) ((c).find(x) != (c).end())
typedef pair<int, int> pii;
typedef long long ll;
template<class T> bool cmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template<class T> bool cmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }

const int N = 3005;

int n, m;
char G[N][N];

int get(int i, int j) {
  return i >= 0 && i < n && j >= 0 && j < m ? G[i][j] : 'X';
}

int down(int i, int j) {
  return get(i, j) == 'R' && get(i+1,j) == 'G' && get(i+2,j) == 'W';
}

int right(int i, int j) {
  return get(i, j) == 'R' && get(i,j+1) == 'G' && get(i,j+2) == 'W';
}

int main() {
  scanf("%d%d", &n, &m);
  for(int i = 0; i < n; i++) {
    scanf("%s", G[i]);
  }

  // for(int i = 0; i < n; i++) { printf("%d\n", right(i, 0)); }

  int ans = 0;
  for(int ij = 0; ij < n+m-1; ij++) {
    // 0 ... right , 1 ... down
    int dp[2][2] = {}; // ij-2, ij-1
    int mx = 0;
    deque<int> prev;
    for(int i = 0; i < n; i++) {
      int j = ij - i;
      if(j < 0 || j >= m || get(i, j) != 'R') {
        continue;
      }

      int nx[2][2] = {};
      int touch2 = SZ(prev) == 2 && prev.front() + 2 == i;
      int touch1 = SZ(prev) >= 1 && prev.back() + 2 >= i;

      // Calc
      for(int d2 = 0; d2 < 2; d2++) {
        for(int d1 = 0; d1 < 2; d1++) {
          int ok = !(d1 && touch1) && !(d2 && touch2);
          cmax(nx[d1][0], dp[d2][d1] + ok * right(i, j));
          cmax(nx[d1][1], dp[d2][d1] + down(i, j));
        }
      }

      // Copy
      for(int d2 = 0; d2 < 2; d2++) {
        for(int d1 = 0; d1 < 2; d1++) {
          dp[d2][d1] = nx[d2][d1];
          cmax(mx, dp[d2][d1]);
        }
      }

      if(SZ(prev) == 2) {
        prev.pop_front();
      }
      prev.emplace_back(i);
    }
    // printf("ij=%d mx=%d\n", ij, mx);
    ans += mx;
  }
  printf("%d\n", ans);
  return 0;
}

Compilation message

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~
dango_maker.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", G[i]);
     ~~~~~^~~~~~~~~~~~

Subtask #1
13.0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	516 KB	Output is correct
3	Correct	2 ms	568 KB	Output is correct
4	Correct	2 ms	568 KB	Output is correct
5	Correct	2 ms	708 KB	Output is correct
6	Correct	2 ms	708 KB	Output is correct
7	Correct	2 ms	708 KB	Output is correct
8	Correct	2 ms	708 KB	Output is correct
9	Correct	3 ms	708 KB	Output is correct
10	Correct	2 ms	708 KB	Output is correct
11	Correct	2 ms	708 KB	Output is correct
12	Correct	2 ms	708 KB	Output is correct
13	Correct	3 ms	708 KB	Output is correct
14	Correct	2 ms	784 KB	Output is correct
15	Correct	2 ms	784 KB	Output is correct
16	Correct	2 ms	784 KB	Output is correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	516 KB	Output is correct
3	Correct	2 ms	568 KB	Output is correct
4	Correct	2 ms	568 KB	Output is correct
5	Correct	2 ms	708 KB	Output is correct
6	Correct	2 ms	708 KB	Output is correct
7	Correct	2 ms	708 KB	Output is correct
8	Correct	2 ms	708 KB	Output is correct
9	Correct	3 ms	708 KB	Output is correct
10	Correct	2 ms	708 KB	Output is correct
11	Correct	2 ms	708 KB	Output is correct
12	Correct	2 ms	708 KB	Output is correct
13	Correct	3 ms	708 KB	Output is correct
14	Correct	2 ms	784 KB	Output is correct
15	Correct	2 ms	784 KB	Output is correct
16	Correct	2 ms	784 KB	Output is correct
17	Correct	2 ms	784 KB	Output is correct
18	Correct	2 ms	812 KB	Output is correct
19	Correct	2 ms	816 KB	Output is correct
20	Correct	2 ms	816 KB	Output is correct
21	Correct	2 ms	816 KB	Output is correct
22	Correct	2 ms	816 KB	Output is correct
23	Correct	2 ms	816 KB	Output is correct
24	Correct	2 ms	816 KB	Output is correct
25	Correct	2 ms	816 KB	Output is correct
26	Correct	2 ms	816 KB	Output is correct
27	Correct	2 ms	816 KB	Output is correct
28	Correct	2 ms	816 KB	Output is correct
29	Correct	2 ms	816 KB	Output is correct
30	Correct	2 ms	816 KB	Output is correct
31	Correct	2 ms	816 KB	Output is correct
32	Correct	2 ms	816 KB	Output is correct
33	Correct	2 ms	816 KB	Output is correct
34	Correct	2 ms	816 KB	Output is correct
35	Correct	2 ms	816 KB	Output is correct
36	Correct	2 ms	816 KB	Output is correct
37	Correct	2 ms	816 KB	Output is correct
38	Correct	2 ms	816 KB	Output is correct
39	Correct	2 ms	816 KB	Output is correct
40	Correct	2 ms	816 KB	Output is correct
41	Correct	2 ms	816 KB	Output is correct
42	Correct	2 ms	816 KB	Output is correct
43	Correct	2 ms	816 KB	Output is correct
44	Correct	2 ms	816 KB	Output is correct
45	Correct	2 ms	816 KB	Output is correct
46	Correct	2 ms	816 KB	Output is correct
47	Correct	2 ms	816 KB	Output is correct
48	Correct	3 ms	820 KB	Output is correct
49	Correct	2 ms	824 KB	Output is correct
50	Correct	2 ms	828 KB	Output is correct
51	Correct	2 ms	828 KB	Output is correct
52	Correct	2 ms	840 KB	Output is correct
53	Correct	2 ms	948 KB	Output is correct

Subtask #3
67.0 / 67.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	3 ms	516 KB	Output is correct
3	Correct	2 ms	568 KB	Output is correct
4	Correct	2 ms	568 KB	Output is correct
5	Correct	2 ms	708 KB	Output is correct
6	Correct	2 ms	708 KB	Output is correct
7	Correct	2 ms	708 KB	Output is correct
8	Correct	2 ms	708 KB	Output is correct
9	Correct	3 ms	708 KB	Output is correct
10	Correct	2 ms	708 KB	Output is correct
11	Correct	2 ms	708 KB	Output is correct
12	Correct	2 ms	708 KB	Output is correct
13	Correct	3 ms	708 KB	Output is correct
14	Correct	2 ms	784 KB	Output is correct
15	Correct	2 ms	784 KB	Output is correct
16	Correct	2 ms	784 KB	Output is correct
17	Correct	2 ms	784 KB	Output is correct
18	Correct	2 ms	812 KB	Output is correct
19	Correct	2 ms	816 KB	Output is correct
20	Correct	2 ms	816 KB	Output is correct
21	Correct	2 ms	816 KB	Output is correct
22	Correct	2 ms	816 KB	Output is correct
23	Correct	2 ms	816 KB	Output is correct
24	Correct	2 ms	816 KB	Output is correct
25	Correct	2 ms	816 KB	Output is correct
26	Correct	2 ms	816 KB	Output is correct
27	Correct	2 ms	816 KB	Output is correct
28	Correct	2 ms	816 KB	Output is correct
29	Correct	2 ms	816 KB	Output is correct
30	Correct	2 ms	816 KB	Output is correct
31	Correct	2 ms	816 KB	Output is correct
32	Correct	2 ms	816 KB	Output is correct
33	Correct	2 ms	816 KB	Output is correct
34	Correct	2 ms	816 KB	Output is correct
35	Correct	2 ms	816 KB	Output is correct
36	Correct	2 ms	816 KB	Output is correct
37	Correct	2 ms	816 KB	Output is correct
38	Correct	2 ms	816 KB	Output is correct
39	Correct	2 ms	816 KB	Output is correct
40	Correct	2 ms	816 KB	Output is correct
41	Correct	2 ms	816 KB	Output is correct
42	Correct	2 ms	816 KB	Output is correct
43	Correct	2 ms	816 KB	Output is correct
44	Correct	2 ms	816 KB	Output is correct
45	Correct	2 ms	816 KB	Output is correct
46	Correct	2 ms	816 KB	Output is correct
47	Correct	2 ms	816 KB	Output is correct
48	Correct	3 ms	820 KB	Output is correct
49	Correct	2 ms	824 KB	Output is correct
50	Correct	2 ms	828 KB	Output is correct
51	Correct	2 ms	828 KB	Output is correct
52	Correct	2 ms	840 KB	Output is correct
53	Correct	2 ms	948 KB	Output is correct
54	Correct	2 ms	948 KB	Output is correct
55	Correct	17 ms	9552 KB	Output is correct
56	Correct	3 ms	9552 KB	Output is correct
57	Correct	11 ms	9552 KB	Output is correct
58	Correct	55 ms	9552 KB	Output is correct
59	Correct	466 ms	19520 KB	Output is correct
60	Correct	466 ms	28380 KB	Output is correct
61	Correct	515 ms	37212 KB	Output is correct
62	Correct	3 ms	37212 KB	Output is correct
63	Correct	487 ms	45704 KB	Output is correct
64	Correct	414 ms	54432 KB	Output is correct
65	Correct	452 ms	63328 KB	Output is correct
66	Correct	450 ms	72136 KB	Output is correct
67	Correct	465 ms	80996 KB	Output is correct
68	Correct	403 ms	89680 KB	Output is correct
69	Correct	424 ms	98676 KB	Output is correct
70	Correct	75 ms	98676 KB	Output is correct
71	Correct	49 ms	98676 KB	Output is correct
72	Correct	51 ms	98676 KB	Output is correct
73	Correct	51 ms	98676 KB	Output is correct
74	Correct	51 ms	98676 KB	Output is correct
75	Correct	51 ms	98676 KB	Output is correct
76	Correct	49 ms	99524 KB	Output is correct
77	Correct	51 ms	100552 KB	Output is correct
78	Correct	47 ms	101480 KB	Output is correct
79	Correct	51 ms	102460 KB	Output is correct
80	Correct	54 ms	103440 KB	Output is correct
81	Correct	51 ms	104420 KB	Output is correct
82	Correct	53 ms	105416 KB	Output is correct
83	Correct	51 ms	106524 KB	Output is correct
84	Correct	60 ms	107376 KB	Output is correct
85	Correct	50 ms	108456 KB	Output is correct
86	Correct	54 ms	109436 KB	Output is correct
87	Correct	51 ms	110348 KB	Output is correct
88	Correct	54 ms	111328 KB	Output is correct
89	Correct	53 ms	112308 KB	Output is correct
90	Correct	56 ms	113288 KB	Output is correct

답안 #74597

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