Submission #519442

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
519442	2022-01-26 11:28:42	AdamGS	Mecho (IOI09_mecho)	C++17	38 / 100	193 ms	7024 KiB

mecho

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=807, INF=1e9+7;
int dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1};
string T[LIM];
int odl[LIM][LIM], wolne[LIM][LIM], n, s;
bool pole(int a, int b) {
  return 0<=a && a<n && 0<=b && b<n;
}
bool ok(int x) {
  queue<pair<int,int>>q;
  rep(i, n) rep(j, n) {
    if(T[i][j]=='M') {
      q.push({i, j});
      odl[i][j]=x*s;
    } else odl[i][j]=INF;
  }
  while(!q.empty()) {
    int a=q.front().st, b=q.front().nd; q.pop();
    if(odl[a][b]>wolne[a][b]) continue;
    if(T[a][b]=='D') return true;
    rep(i, 4) if(pole(a+dx[i], b+dy[i])) {
      if((T[a+dx[i]][b+dy[i]]=='G' || T[a+dx[i]][b+dy[i]]=='D') && odl[a+dx[i]][b+dy[i]]==INF) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 38 / 100