Submission #977529

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
977529	2024-05-08 06:20:57	farica	Mecho (IOI09_mecho)	C++14	25 / 100	1089 ms	7252 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>
#define int long long
using namespace std;
const int MAX_N = 4e5 + 5;
int n, s, dist[800][800], sx, sy;
string grid[800];
bool test(int m) {
    priority_queue<pair<int, pair<int,int>>>pq;
    vector<vector<bool>>visited(n, vector<bool>(n, 0));
    pq.push({0, {sx, sy}});
    while(!pq.empty()) {
        int x = pq.top().second.first, y = pq.top().second.second, cnt = -1 * pq.top().first;
        pq.pop();
        if(visited[x][y]) continue;
        visited[x][y] = 1;
        if(grid[x][y] == 'D') return true;
        int cost = ((cnt+1) / s) + ((cnt+1) % s > 0 ? 1 : 0) + m;
        if(x && grid[x-1][y] != 'T' && dist[x-1][y] >= cost) pq.push({(cnt + 1) * -1, {x-1, y}});
        if(y && grid[x][y-1] != 'T' && dist[x][y-1] >= cost) pq.push({(cnt + 1) * -1, {x, y-1}});
        if(x+1<n && grid[x+1][y] != 'T' && dist[x+1][y] >= cost) pq.push({(cnt + 1) * -1, {x+1, y}});
        if(y+1<n && grid[x][y+1] != 'T' && dist[x][y+1] >= cost) pq.push({(cnt + 1) * -1, {x, y+1}});
    }
    return false;
}
void solve() {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 25 / 100