fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5. long long n , maxx , pp , m , q ;
  6. long long arr[100007] ;
  7. long long lis[100];
  8. long long dp [ 106 ][ 106 ][6] ,  room[106][106], magic [106][106];
  9. pair < int , int > must[103]  ;
  10. bool ok1 = false ;
  11. long long solve (int i , int j , int l )
  12. {
  13.     if ( i == n && j == m &&  ( l==1 || magic[n][m] ) )
  14.         return room [ n ][m] ;
  15.     if ( i> n || j > m)
  16.         return -1e10 ;
  17.     if ( magic[i][j] )
  18.             l=1 ;
  19.     if ( dp[ i ] [ j ][ l ]!=-1e9)
  20.         return dp[ i ][ j ][ l ];
  21.     return dp[ i ][ j ][ l ] = max (solve( i , j+1 , l)+room [ i ][j] , solve(i+1 , j , l )+room [ i ][ j ]);
  22. }
  23.  
  24. int main()
  25. {
  26.     int l ;
  27.     cin >> l ;
  28.     while (l--){
  29.             ok1 = false ;
  30.             memset(magic ,0 ,sizeof magic);
  31.     cin >> n >> m >> q ;
  32.      for(int i=0; i<=n; i++) for(int j=0; j<=m; j++) for(int k=0; k<2; k++) dp[i][j][k] = -1e9;
  33.     for (int i=0 ; i<q ; i++ ){
  34.         int x,y; cin>>x>>y;
  35.     magic[x][y] = 1;}
  36.     for(int i=1 ; i<=n ; i++ )
  37.         for (int j = 1 ; j<=m ; j++ )
  38.             cin >> room[i][j] ;
  39.     cout << solve( 1 , 1 , 0)<<"\n";
  40.     }
  41.     return 0;
  42. }
  43.  
Success #stdin #stdout 0s 16720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/11Uafc
language:
C++14 (clang 8.0)
created:
7 years 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!