Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 1e3 + 10;
- const int M = 1e3 + 10;
- int ar[N][M], Max[N][M], Count[N][M];
- int n, m;
- int main(){
- scanf("%d%d", &n, &m);
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- scanf("%d", &ar[i][j]);
- }
- }
- for(int j=1;j<=m;j++){
- Max[1][j] = ar[1][j];
- Count[1][j] = 1;
- }
- for(int i=2;i<=n;i++){
- for(int j=1;j<=m;j++){
- int l, r;
- if(i % 2 == 1) l = j - 1, r = j;
- else l = j, r = j + 1;
- if(Max[i-1][l] == Max[i-1][r]) Count[i][j] = Count[i-1][l] + Count[i-1][r];
- else if(Max[i-1][l] > Max[i-1][r]) Count[i][j] = Count[i-1][l];
- else Count[i][j] = Count[i-1][r];
- Max[i][j] = ar[i][j] + max(Max[i-1][l], Max[i-1][r]);
- }
- }
- int mx = 0;
- for(int j=1;j<=m;j++)
- mx = max(mx, Max[n][j]);
- int cnt = 0;
- for(int j=1;j<=m;j++)
- if(Max[n][j] == mx) cnt += Count[n][j];
- printf("%d %d", mx, cnt);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement