oj.uz

답안 #631646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631646 2022-08-18T11:20:14 Z Abrar_Al_Samit Soccer (JOI17_soccer) C++17
30 / 100
 331 ms 18588 KB 
#include<bits/stdc++.h>
using namespace std;

const int MX = 505;
const long long INF = 1e18;

int h, w;
int n; 
long long A, B, C;
long long nearest[MX][MX];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
//0->down, 1->up, 2->right, 3->left
long long dist[MX][MX][5];
void PlayGround() {
  cin>>h>>w;
  cin>>A>>B>>C;
  cin>>n;

  for(int i=0; i<=h; ++i) {
    for(int j=0; j<=w; ++j) {
      nearest[i][j] = INF;

      for(int k=0; k<5; ++k) {
        dist[i][j][k] = INF;
      }
    }
  }

  auto valid = [&] (int i, int j) {
    return i<=h && i>-1 && j>-1 && j<=w;
  };

  vector<pair<int,int>>oneandn;

  queue<pair<int,int>>q;
  for(int i=0; i<n; ++i) {
    int x, y;
    cin>>x>>y;
    nearest[x][y] = 0;
    q.emplace(x, y);
    if(oneandn.size()==2) oneandn.pop_back();
    oneandn.emplace_back(x, y);
  }

  while(!q.empty()) {
    int x, y;
    tie(x, y) = q.front(); q.pop();
    for(int j=0; j<4; ++j) {
      int newx = x + dx[j], newy = y + dy[j];
      if(valid(newx, newy)) {
        if(nearest[newx][newy]>nearest[x][y]+1) {
          nearest[newx][newy] = nearest[x][y]+1;
          q.emplace(newx, newy);
        }
      }
    }
  }

  dist[oneandn[0].first][oneandn[0].second][0] = 0;
  priority_queue<tuple<long long, int, int, int>>pq;
  pq.emplace(0, oneandn[0].first, oneandn[0].second, 0);
  while(!pq.empty()) {
    long long cost;
    int x, y, dir;
    tie(cost, x, y, dir) = pq.top(); pq.pop();
    cost = -cost;
    if(cost!=dist[x][y][dir]) continue;

    if(dir) {
      int newx = x + dx[dir-1], newy = y + dy[dir-1];
      if(valid(newx, newy)) {
        if(dist[newx][newy][dir]>cost) { //continue travelling
          dist[newx][newy][dir] = cost;
          pq.emplace(-cost, newx, newy, dir);
        }
      }
      if(dist[x][y][0]>cost+nearest[x][y]*C) { //stop and call a player
        dist[x][y][0] = cost+nearest[x][y]*C;
        pq.emplace(-dist[x][y][0], x, y, 0);
      }
    } else {
      for(int j=0; j<4; ++j) {
        int newx = x + dx[j], newy = y + dy[j];
        if(valid(newx, newy)) {
          if(dist[newx][newy][0]>cost+C) { //run
            dist[newx][newy][0] = cost+C;
            pq.emplace(-cost-C, newx, newy, 0);
          }
          if(dist[newx][newy][j+1]>cost+B) { //kick
            dist[newx][newy][j+1] = cost+B;
            pq.emplace(-cost-B, newx, newy, j+1);
          }
        }
      }
    }
  }

  long long ans = INF;
  for(int k=0; k<5; ++k) {
    ans = min(ans, dist[oneandn[1].first][oneandn[1].second][k]);
  }
  cout<<ans<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 6736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 321 ms 18448 KB Output is correct
2 Correct 329 ms 18500 KB Output is correct
3 Correct 229 ms 16112 KB Output is correct
4 Correct 248 ms 18468 KB Output is correct
5 Correct 249 ms 18436 KB Output is correct
6 Correct 244 ms 18484 KB Output is correct
7 Correct 331 ms 18588 KB Output is correct
8 Correct 296 ms 18520 KB Output is correct
9 Correct 331 ms 18588 KB Output is correct
10 Correct 52 ms 7700 KB Output is correct
11 Correct 313 ms 18528 KB Output is correct
12 Correct 317 ms 18516 KB Output is correct
13 Correct 197 ms 16096 KB Output is correct
14 Correct 302 ms 18532 KB Output is correct
15 Correct 244 ms 18536 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 6736 KB Output isn't correct
2 Halted 0 ms 0 KB -