Submission #1692756
Source Code Expand
//2017-10-18
//miaomiao
//
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
#define For(i, a, b) for(int i = (a); i <= (int)(b); ++i)
#define N (100+2)
char mp[N][N];
short f[N][N][N][N], sumr[N][N], sumc[N][N];
inline short Calc(short *sum, int l, int r){
if(l > r) return 0;
// printf("add = %d\n", sum[r] - sum[l-1]);
return sum[r] - sum[l-1];
}
inline void Add(short &me, short add){
if(me < add) me = add;
}
int main(){
int n, m, ex, ey;
scanf("%d%d", &n, &m);
For(i, 1, n){
scanf("%s", mp[i]+1);
For(j, 1, m){
sumr[i][j] = sumr[i][j-1] + (mp[i][j]=='o');
if(mp[i][j] == 'E') ex = i, ey = j;
}
}
For(i, 1, m) For(j, 1, n) sumc[i][j] = sumc[i][j-1] + (mp[j][i]=='o');
// printf("ex = %d ey = %d\n", ex, ey);
int ans = 0, A = ex-1, B = n-ex, C = ey-1, D = m-ey;
int me, nxt;
For(a, 0, A) For(b, 0, B) For(c, 0, C) For(d, 0, D){
ans = max(ans, me = f[a][b][c][d]);
// printf("f[%d][%d][%d][%d] = %d\n", a, b, c, d, f[a][b][c][d]);
nxt = 0;
if(a < A){
// puts("UP");
if(ex-a-1 > b) nxt = Calc(sumr[ex-a-1], max(d+1,ey-c), min(m-c,ey+d));
Add(f[a+1][b][c][d], nxt+me);
}
nxt = 0;
if(b < B){
// puts("DOWN");
if(ex+b+1 < n-a+1) nxt = Calc(sumr[ex+b+1], max(d+1,ey-c), min(m-c,ey+d));
Add(f[a][b+1][c][d], nxt+me);
}
nxt = 0;
if(c < C){
// puts("LEFT");
if(ey-c-1 > d) nxt = Calc(sumc[ey-c-1], max(b+1,ex-a), min(n-a,ex+b));
Add(f[a][b][c+1][d], nxt+me);
}
nxt = 0;
if(d < D){
// puts("RIGHT");
if(ey+d+1 < m-c+1) nxt = Calc(sumc[ey+d+1], max(b+1,ex-a), min(n-a,ex+b));
Add(f[a][b][c][d+1], nxt+me);
}
// puts("====================="); puts("");
}
printf("%d\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Salvage Robots |
User |
miaomiao |
Language |
C++14 (GCC 5.4.1) |
Score |
1400 |
Code Size |
1851 Byte |
Status |
AC |
Exec Time |
109 ms |
Memory |
203008 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:32:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &m);
^
./Main.cpp:34:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", mp[i]+1);
^
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1400 / 1400 |
Status |
|
|
Set Name |
Test Cases |
Sample |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt |
All |
0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt, 1_55.txt, 1_56.txt, 1_57.txt, 1_58.txt, 1_59.txt, 1_60.txt, 1_61.txt, 1_62.txt, 1_63.txt, 1_64.txt, 1_65.txt, 1_66.txt, 1_67.txt, 1_68.txt, 1_69.txt, 1_70.txt, 1_71.txt |
Case Name |
Status |
Exec Time |
Memory |
0_00.txt |
AC |
2 ms |
2304 KB |
0_01.txt |
AC |
1 ms |
256 KB |
0_02.txt |
AC |
2 ms |
4352 KB |
0_03.txt |
AC |
2 ms |
4352 KB |
1_00.txt |
AC |
1 ms |
256 KB |
1_01.txt |
AC |
1 ms |
256 KB |
1_02.txt |
AC |
2 ms |
2304 KB |
1_03.txt |
AC |
2 ms |
2304 KB |
1_04.txt |
AC |
2 ms |
2688 KB |
1_05.txt |
AC |
3 ms |
4352 KB |
1_06.txt |
AC |
29 ms |
86528 KB |
1_07.txt |
AC |
28 ms |
87680 KB |
1_08.txt |
AC |
101 ms |
104064 KB |
1_09.txt |
AC |
48 ms |
102528 KB |
1_10.txt |
AC |
13 ms |
15232 KB |
1_11.txt |
AC |
55 ms |
105088 KB |
1_12.txt |
AC |
48 ms |
48768 KB |
1_13.txt |
AC |
33 ms |
84480 KB |
1_14.txt |
AC |
57 ms |
105472 KB |
1_15.txt |
AC |
11 ms |
5632 KB |
1_16.txt |
AC |
69 ms |
81024 KB |
1_17.txt |
AC |
25 ms |
46720 KB |
1_18.txt |
AC |
55 ms |
116480 KB |
1_19.txt |
AC |
61 ms |
92800 KB |
1_20.txt |
AC |
99 ms |
151936 KB |
1_21.txt |
AC |
93 ms |
160384 KB |
1_22.txt |
AC |
72 ms |
127488 KB |
1_23.txt |
AC |
82 ms |
186752 KB |
1_24.txt |
AC |
68 ms |
196864 KB |
1_25.txt |
AC |
62 ms |
199040 KB |
1_26.txt |
AC |
4 ms |
4864 KB |
1_27.txt |
AC |
6 ms |
8448 KB |
1_28.txt |
AC |
56 ms |
180608 KB |
1_29.txt |
AC |
62 ms |
184704 KB |
1_30.txt |
AC |
52 ms |
166272 KB |
1_31.txt |
AC |
57 ms |
176512 KB |
1_32.txt |
AC |
59 ms |
184576 KB |
1_33.txt |
AC |
4 ms |
4352 KB |
1_34.txt |
AC |
63 ms |
203008 KB |
1_35.txt |
AC |
64 ms |
186880 KB |
1_36.txt |
AC |
8 ms |
16512 KB |
1_37.txt |
AC |
2 ms |
640 KB |
1_38.txt |
AC |
60 ms |
194816 KB |
1_39.txt |
AC |
8 ms |
10368 KB |
1_40.txt |
AC |
109 ms |
107520 KB |
1_41.txt |
AC |
102 ms |
107520 KB |
1_42.txt |
AC |
86 ms |
101248 KB |
1_43.txt |
AC |
94 ms |
95232 KB |
1_44.txt |
AC |
84 ms |
88960 KB |
1_45.txt |
AC |
106 ms |
123648 KB |
1_46.txt |
AC |
103 ms |
95232 KB |
1_47.txt |
AC |
91 ms |
97280 KB |
1_48.txt |
AC |
91 ms |
91136 KB |
1_49.txt |
AC |
107 ms |
105472 KB |
1_50.txt |
AC |
90 ms |
97152 KB |
1_51.txt |
AC |
96 ms |
109440 KB |
1_52.txt |
AC |
94 ms |
91136 KB |
1_53.txt |
AC |
109 ms |
109440 KB |
1_54.txt |
AC |
98 ms |
107264 KB |
1_55.txt |
AC |
96 ms |
97280 KB |
1_56.txt |
AC |
52 ms |
50816 KB |
1_57.txt |
AC |
98 ms |
150272 KB |
1_58.txt |
AC |
53 ms |
52864 KB |
1_59.txt |
AC |
83 ms |
152064 KB |
1_60.txt |
AC |
88 ms |
154112 KB |
1_61.txt |
AC |
31 ms |
35584 KB |
1_62.txt |
AC |
92 ms |
154368 KB |
1_63.txt |
AC |
84 ms |
148224 KB |
1_64.txt |
AC |
61 ms |
121344 KB |
1_65.txt |
AC |
44 ms |
44672 KB |
1_66.txt |
AC |
80 ms |
144128 KB |
1_67.txt |
AC |
69 ms |
123648 KB |
1_68.txt |
AC |
83 ms |
146176 KB |
1_69.txt |
AC |
75 ms |
140032 KB |
1_70.txt |
AC |
85 ms |
145920 KB |
1_71.txt |
AC |
81 ms |
145920 KB |