fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  5. #define endl "\n"
  6. #define pb push_back
  7. #define ppb pop_back
  8. #define mp make_pair
  9. #define ff first
  10. #define ss second
  11. #define all(x) (x).begin(), (x).end()
  12. #define allr(x) (x).rbegin(),(x).rend()
  13. #define sz(x) ((int)(x).size())
  14. #define vi vector<int>
  15. #define vvi vector<vector<int>>
  16. #define vll vector<ll>
  17. #define vvll vector<vector<ll>>
  18. #define pi pair<int,int>
  19. #define pll pair<ll,ll>
  20. #define umap unordered_map
  21. #define uset unordered_set
  22.  
  23. typedef long long ll;
  24. typedef unsigned long long ull;
  25. typedef long double lld;
  26.  
  27. /***************************************************************************************************************************************************/
  28.                                 /**DEBUG**/
  29. #ifndef ONLINE_JUDGE
  30. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  31. #else
  32. #define debug(x)
  33. #endif
  34.  
  35. void _print(ll t) {cerr << t;}
  36. void _print(int t) {cerr << t;}
  37. void _print(string t) {cerr << t;}
  38. void _print(char t) {cerr << t;}
  39. void _print(lld t) {cerr << t;}
  40. void _print(double t) {cerr << t;}
  41. void _print(ull t) {cerr << t;}
  42.  
  43. template <class T, class V> void _print(pair <T, V> p);
  44. template <class T> void _print(vector <T> v);
  45. template <class T> void _print(set <T> v);
  46. template <class T, class V> void _print(map <T, V> v);
  47. template <class T> void _print(multiset <T> v);
  48. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
  49. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  50. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  51. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  52. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  53. /***************************************************************************************************************************************************/
  54. /*                          author : drkspark                   */
  55. /*url :                     */
  56.  
  57.  
  58. int main() {
  59. fastio;
  60. // #ifndef ONLINE_JUDGE
  61. // freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); freopen("error.txt", "w", stderr);
  62. // #endif
  63.     int t;  
  64.     cin >> t;
  65.     while(t--){
  66.         int row,col;
  67.         cin >> row >> col;
  68.         vvll mat(row,vll(col));         
  69.         for(int i=0;i<row;i++){
  70.             for(int j=0; j<col;j++){
  71.                 cin >> mat[i][j];
  72.             }
  73.         }
  74.         ll val = 0;
  75.         if(mat[0][0] <0 || mat[row-1][col-1] <0){
  76.             cout << -1 << endl;
  77.             continue;
  78.         }
  79.         // Filling 1st row
  80.         for(int i=1; i<col; i++){
  81.             if(val == -1){
  82.                 mat[0][i] = -1;
  83.                 continue;
  84.             }
  85.  
  86.             if(mat[0][i] <0){
  87.                 val = -1;
  88.                 continue;
  89.             }
  90.  
  91.             mat[0][i] += mat[0][i-1]; 
  92.         }
  93.  
  94.         val = 0;
  95.  
  96.         for(int i=1; i<row; i++){
  97.             if(val == -1){
  98.                 mat[i][0] = -1;
  99.                 continue;
  100.             }
  101.  
  102.             if(mat[i][0] <0){
  103.                 val = -1;
  104.                 continue;
  105.             }
  106.  
  107.             mat[i][0] += mat[i-1][0]; 
  108.         }
  109.  
  110.         // debug(mat);
  111.         for(int i=1; i<row; i++){
  112.             for(int j=1; j<col; j++){
  113.                 if(mat[i][j] <0){//mat[i][j] == -1
  114.                     continue;
  115.                 }
  116.                 ll val = max(max(mat[i-1][j],mat[i][j-1]),mat[i-1][j-1]);//added diagonal case
  117.                 if(val <0){//val == -1LL (val is not always -1 it may be any -ve number)
  118.                     mat[i][j] = -1;
  119.                 }
  120.                 else{
  121.                     mat[i][j] += val;
  122.                 }
  123.             }
  124.         }
  125.         if(mat[row-1][col-1]==-1){
  126.             cout<<-1<<endl;
  127.             continue;
  128.         }
  129.         cout << mat[row-1][col-1] << endl;
  130.     }
  131.     return 0;
  132. }
Success #stdin #stdout 0.01s 5440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kh8sn4
language:
C++14 (gcc 8.3)
created:
1 year 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!