fork(7) download
copy 
  1. /*
  2. written by- Piyush Golani
  3. language- c++
  4. country- India
  5. College- N.I.T Jamshedpur
  6. */
  7. #include <cmath>
  8. #include <ctime>
  9. #include <iostream>
  10. #include <string>
  11. #include <vector>
  12. #include<cstdio>
  13. #include<sstream>
  14. #include<algorithm>
  15. #include<cstdlib>
  16. #include<cstring>
  17. #include<map>
  18. #include<cctype>
  19. #include<queue>
  20. using namespace std;
  21. #define pb push_back
  22. #define all(s) s.begin(),s.end()
  23. #define f(i,a,b) for(int i=a;i<b;i++)
  24. #define F(i,a,b) for(int i=a;i>=b;i--)
  25. #define PI 3.1415926535897932384626433832795
  26. #define INF 1000000005
  27. #define BIG_INF 7000000000000000000LL
  28. #define mp make_pair
  29. #define eps 1e-9
  30. #define LL long long
  31. #define si(n) scanf("%d",&n)
  32. #define sll(n) scanf("%lld",&n)
  33. #define mod 1000000007
  34. #define vv pair<LL,int>
  35.  
  36. int A[55][55];
  37. int n,m;
  38. LL sumrow[55][55][55],sumcol[55][55][55],Al,Bo;
  39. LL DP[55][55][55][55];
  40. LL Do(int r1,int r2,int c1,int c2)
  41. {
  42.     LL &res=DP[r1][r2][c1][c2];
  43.     if(res!=-1) return res;
  44.     //Alice
  45.     if(r1>r2 || c1>c2 || r1>=n || r2<0 || c1<0 || c2>=m) return res=0;
  46.     char e;
  47.     int y;
  48.     int p=INF;
  49.     //cout<<r1<<" "<<r2<<" "<<c1<<" "<<c2<<"\n";
  50.     if(sumrow[r1][c1][c2]<p)
  51.     {
  52.         p=sumrow[r1][c1][c2];
  53.         e='r';
  54.         y=1;
  55.     }
  56.     if(sumrow[r2][c1][c2]<p)
  57.     {
  58.         p=sumrow[r2][c1][c2];
  59.         e='r';
  60.         y=2;
  61.     }
  62.     if(sumcol[c1][r1][r2]<p)
  63.     {
  64.         p=sumcol[c1][r1][r2];
  65.         e='c';
  66.         y=1;
  67.     }
  68.     if(sumcol[c2][r1][r2]<p)
  69.     {
  70.         p=sumcol[c2][r1][r2];
  71.         e='c';
  72.         y=2;
  73.     }
  74.     //see which one is chosen
  75.     if(e=='r')
  76.     {
  77.         if(y==1)
  78.         {
  79.             //Al+=sumrow[r1][c1][c2];
  80.             r1++;
  81.         }
  82.         else
  83.         {
  84.             //Al+=sumrow[r2][c1][c2];
  85.             r2--;
  86.         }
  87.     }
  88.     else
  89.     {
  90.         if(y==1)
  91.         {
  92.             //Al+=sumcol[c1][r1][r2];
  93.             c1++;
  94.         }
  95.         else
  96.         {
  97.             //Al+=sumcol[c2][r1][r2];
  98.             c2--;
  99.         }
  100.     }
  101.     LL a=0;
  102.     if(r1<=r2 && c1<=c2 && c1<m && c2>=0 && r1<n && r2>=0)
  103.     {
  104.         a=max(max(sumrow[r1][c1][c2]+Do(r1+1,r2,c1,c2),sumrow[r2][c1][c2]+Do(r1,r2-1,c1,c2)),max(sumcol[c1][r1][r2]+Do(r1,r2,c1+1,c2),sumcol[c2][r1][r2]+Do(r1,r2,c1,c2-1)));
  105.  
  106.     }
  107.  
  108.     return res=a;
  109. }
  110.  
  111. int main()
  112. {
  113.     int t;
  114.     si(t);
  115.     while(t--)
  116.     {
  117.         si(n); si(m);
  118.         LL sum=0;
  119.         f(i,0,n)
  120.         {
  121.             f(j,0,m)
  122.             {
  123.                 si(A[i][j]);
  124.                 sum+=A[i][j];
  125.             }
  126.         }
  127.  
  128.         f(i,0,n)
  129.         {
  130.             f(j,0,m)
  131.             {
  132.                 f(k,0,m)
  133.                 {
  134.                     if(j==k)
  135.                     {
  136.                         sumrow[i][j][k]=A[i][j];
  137.                         continue;
  138.                     }
  139.                     sumrow[i][j][k]=sumrow[i][j][k-1]+A[i][k];
  140.                 }
  141.             }
  142.         }
  143.         f(i,0,m)
  144.         {
  145.             f(j,0,n)
  146.             {
  147.                 f(k,0,n)
  148.                 {
  149.                     if(j==k)
  150.                     {
  151.                         sumcol[i][j][k]=A[j][i];
  152.                         continue;
  153.                     }
  154.                     sumcol[i][j][k]=sumcol[i][j][k-1]+A[k][i];
  155.                 }
  156.             }
  157.         }
  158.         //Al=0,Bo=0;
  159.         memset(DP,-1,sizeof(DP));
  160.         Bo=Do(0,n-1,0,m-1);
  161.         Al=sum-Bo;
  162.         //cout<<Al<<" "<<Bo<<"\n";
  163.         if(Al==Bo) Bo+=Al;
  164.         printf("%lld\n",max(Al,Bo));
  165.     }
  166.     return 0;
  167. }
  168.  
Time limit exceeded #stdin #stdout 5s 76864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4CReZE
language:
C++ (gcc 8.3)
created:
11 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!