fork download 
  1. // ~~ icebear ~~
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7. typedef pair<int, ii> iii;
  8.  
  9. template<class T>
  10.     bool minimize(T &a, const T &b) {
  11.         if (a > b) return a = b, true;
  12.         return false;
  13.     }
  14.  
  15. template<class T>
  16.     bool maximize(T &a, const T &b) {
  17.         if (a < b) return a = b, true;
  18.         return false;
  19.     }
  20.  
  21. #define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
  22. #define FORR(i,a,b) for(int i=(a); i>=(b); --i)
  23. #define REP(i, n) for(int i=0; i<(n); ++i)
  24. #define RED(i, n) for(int i=(n)-1; i>=0; --i)
  25. #define MASK(i) (1LL << (i))
  26. #define BIT(S, i) (((S) >> (i)) & 1)
  27. #define mp make_pair
  28. #define pb push_back
  29. #define fi first
  30. #define se second
  31. #define all(x) x.begin(), x.end()
  32. #define task "icebear"
  33.  
  34. const int MOD = 1e9 + 7;
  35. const int inf = 1e9 + 27092008;
  36. const ll INF = 1e18 + 27092008;
  37. const int dx[] = {0, +1};
  38. const int dy[] = {+1, 0};
  39. const int N = 2000 + 5;
  40. int n, m, r[N], c[N];
  41. ll dist[N][N][2][2]; // f(i, j, r, c): state of row and col
  42. int a[N][N];
  43.  
  44. bool reach(int x, int y, int R, int C) {
  45.     return a[x][y] ^ R ^ C;
  46. }
  47.  
  48. bool inside(int x, int y) {
  49.     return 1 <= x && x <= n && 1 <= y && y <= m;
  50. }
  51.  
  52. void init(void) {
  53.     cin >> n >> m;
  54.     FOR(i, 1, n) FOR(j, 1, m) {
  55.         char x; cin >> x;
  56.         a[i][j] = x - '0';
  57.     }
  58.     FOR(i, 1, n) cin >> r[i];
  59.     FOR(j, 1, m) cin >> c[j];
  60. }
  61.  
  62. void process(void) {
  63.     priority_queue<array<ll, 5>, vector<array<ll, 5>>, greater<array<ll, 5>>> Q;
  64.     memset(dist, 0x3f, sizeof dist);
  65.  
  66.     REP(R, 2) REP(C, 2) if (reach(1, 1, R, C)) {
  67.         dist[1][1][R][C] = R * r[1] + C * c[1];
  68.         Q.push({dist[1][1][R][C], 1, 1, R, C});
  69.     }
  70.  
  71.     while(!Q.empty()) {
  72.         auto T = Q.top(); Q.pop();
  73.         if (T[0] != dist[T[1]][T[2]][T[3]][T[4]]) continue;
  74.         if (T[1] == n && T[2] == m) {
  75.             cout << T[0];
  76.             exit(0);
  77.         }
  78.         REP(i, 2) {
  79.             int x = T[1] + dx[i];
  80.             int y = T[2] + dy[i];
  81.             if (!inside(x, y)) continue;
  82.             if (i == 0) {
  83.                 REP(C, 2)
  84.                     if (reach(x, y, T[3], C) && minimize(dist[x][y][T[3]][C], T[0] + C * c[y]))
  85.                         Q.push({dist[x][y][T[3]][C], x, y, T[3], C});
  86.             } else {
  87.                 REP(R, 2)
  88.                     if (reach(x, y, R, T[4]) && minimize(dist[x][y][R][T[4]], T[0] + R * r[x]))
  89.                         Q.push({dist[x][y][R][T[4]], x, y, R, T[4]});
  90.             }
  91.         }
  92.     }
  93.  
  94.     cout << -1;
  95. }
  96.  
  97. int main() {
  98.     ios_base::sync_with_stdio(0);
  99.     cin.tie(0); cout.tie(0);
  100.     if (fopen(task".inp", "r")) {
  101.         freopen(task".inp", "r", stdin);
  102.         freopen(task".out", "w", stdout);
  103.     }
  104.     int tc = 1;
  105. //    cin >> tc;
  106.     while(tc--) {
  107.         init();
  108.         process();
  109.     }
  110.     return 0;
  111. }
  112.  
  113.  
Success #stdin #stdout 0.02s 131248KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/eRCrYq
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!