Advertisement
YEZAELP

TOI9: beehive

Jul 26th, 2021
1,011
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.07 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e3 + 10;
  5. const int M = 1e3 + 10;
  6. int ar[N][M], Max[N][M], Count[N][M];
  7. int n, m;
  8.  
  9. int main(){
  10.  
  11.     scanf("%d%d", &n, &m);
  12.  
  13.     for(int i=1;i<=n;i++){
  14.         for(int j=1;j<=m;j++){
  15.             scanf("%d", &ar[i][j]);
  16.         }
  17.     }
  18.  
  19.     for(int j=1;j<=m;j++){
  20.         Max[1][j] = ar[1][j];
  21.         Count[1][j] = 1;
  22.     }
  23.  
  24.     for(int i=2;i<=n;i++){
  25.         for(int j=1;j<=m;j++){
  26.             int l, r;
  27.             if(i % 2 == 1) l = j - 1, r = j;
  28.             else l = j, r = j + 1;
  29.             if(Max[i-1][l] == Max[i-1][r]) Count[i][j] = Count[i-1][l] + Count[i-1][r];
  30.             else if(Max[i-1][l] > Max[i-1][r]) Count[i][j] = Count[i-1][l];
  31.             else Count[i][j] = Count[i-1][r];
  32.             Max[i][j] = ar[i][j] + max(Max[i-1][l], Max[i-1][r]);
  33.         }
  34.     }
  35.  
  36.     int mx = 0;
  37.     for(int j=1;j<=m;j++)
  38.         mx = max(mx, Max[n][j]);
  39.  
  40.     int cnt = 0;
  41.     for(int j=1;j<=m;j++)
  42.         if(Max[n][j] == mx) cnt += Count[n][j];
  43.  
  44.     printf("%d %d", mx, cnt);
  45.  
  46.     return 0;
  47. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement