Advertisement
YEZAELP

o64_feb_c1_obstacle

Feb 2nd, 2022
650
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const bool Debug = false;
  6. const int inf = 1e9;
  7. vector <vector <int>> dis(1, vector <int> (1)), rdis(1, vector <int> (1)), mn(1, vector <int> (1));
  8. int n, m;
  9.  
  10. int ask(int I, int J){
  11.     I ++, J ++;
  12.     if(I == n or J == 1) return -1;
  13.     return mn[I + 1][J];
  14. }
  15.  
  16. void initialize(int N, int M, int Q, vector<vector<int>>& rowlen, vector<vector<int>>& collen){
  17.     n = N, m = M;
  18.     dis.resize(N + 5, vector <int> (M + 5)), rdis.resize(N + 5, vector <int> (M + 5)), mn.resize(N + 5, vector <int> (M + 5));
  19.  
  20.     /// 1 - > ed
  21.     for(int i=1;i<=N;i++){
  22.         for(int j=1;j<=M;j++){
  23.             if(i == 1 and j == 1) dis[i][j] = 0;
  24.             else if(i == 1) dis[i][j] = dis[i][j - 1] + rowlen[0][j - 2];
  25.             else if(j == 1) dis[i][j] = dis[i - 1][j] + collen[i - 2][0];
  26.             else dis[i][j] = min(dis[i][j - 1] + rowlen[i - 1][j - 2], dis[i - 1][j] + collen[i - 2][j - 1]);
  27.         }
  28.     }
  29.     if(Debug){
  30.         printf("dis : \n");
  31.         for(int i=1;i<=N;i++){
  32.             for(int j=1;j<=M;j++){
  33.                 printf("%d ", dis[i][j]);
  34.             }
  35.             printf("\n");
  36.         }
  37.     }
  38.  
  39.     /// ed - > 1
  40.     for(int i=N;i>=1;i--){
  41.         for(int j=M;j>=1;j--){
  42.             if(i == N and j == M) rdis[i][j] = 0;
  43.             else if(i == N) rdis[i][j] = rdis[i][j + 1] + rowlen[i - 1][j - 1];
  44.             else if(j == M) rdis[i][j] = rdis[i + 1][j] + collen[i - 1][j - 1];
  45.             else rdis[i][j] = min(rdis[i][j + 1] + rowlen[i - 1][j - 1], rdis[i + 1][j] + collen[i - 1][j - 1]);
  46.         }
  47.     }
  48.     if(Debug){
  49.         printf("rdis : \n");
  50.         for(int i=1;i<=N;i++){
  51.             for(int j=1;j<=M;j++){
  52.                 printf("%d ", rdis[i][j]);
  53.             }
  54.             printf("\n");
  55.         }
  56.     }
  57.  
  58.     for(int i=N;i>=1;i--){
  59.         mn[i][1] = inf;
  60.         for(int j=2;j<=M;j++){
  61.             if(Debug) printf("[ %d ][ %d ] = %d %d %d\n", i, j, dis[i][j - 1], rowlen[i - 1][j - 2], rdis[i][j]);
  62.             mn[i][j] = min(i == N ? inf: mn[i + 1][j], dis[i][j - 1] + rowlen[i - 1][j - 2] + rdis[i][j]);
  63.         }
  64.     }
  65.     if(Debug){
  66.         printf("mn : \n");
  67.         for(int i=1;i<=N;i++){
  68.             for(int j=1;j<=M;j++){
  69.                 if(mn[i][j] == inf) printf("inf ");
  70.                 else printf("%d ", mn[i][j]);
  71.             }
  72.             printf("\n");
  73.         }
  74.     }
  75.  
  76.     if(Debug){
  77.         for(int q=1;q<=Q;q++){
  78.             int I, J;
  79.             scanf("%d %d", &I, &J);
  80.             cout << ask(I, J) << endl;;
  81.         }
  82.     }
  83. }
Advertisement
RAW Paste Data Copied
Advertisement