SHARE
TWEET

b

JoaquinPaste Oct 13th, 2019 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. //#define TEAM
  4.  
  5. #ifdef TEAM
  6. #define deb(...) fprintf(stderr,__VA_ARGS__)
  7. #define deb1(x) cerr << #x << "=" << x << endl
  8. #else
  9. #define deb(...) 0
  10. #define deb1(x) 0
  11. #endif
  12.  
  13. #define pb push_back
  14. #define fs first
  15. #define snd second
  16.  
  17. #define FOR(x,to) for(int x=0;x<(to);x++)
  18. #define F0R(x,in,to) for(int x=(in);x<(to);x++)
  19. #define FORR(x,arr) for(auto& x:arr)
  20. #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
  21. #define ALL(a) (a.begin()),(a.end())
  22. #define ZERO(a) memset(a,0,sizeof(a))
  23. #define MINUS(a) memset(a,0xff,sizeof(a))
  24.  
  25. typedef long long ll;
  26. using namespace std;
  27.  
  28. typedef pair<int,int> ii;
  29. typedef vector<int> vi;
  30.  
  31. template <class Ch, class Tr, class Container>
  32. basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
  33.     os << "{ ";
  34.     for(auto& y : x) os << y << " ";
  35.     return os << "}";
  36. }
  37.  
  38. template <class X, class Y>
  39. ostream & operator << (ostream & os, pair <X, Y> const& p) {
  40.     return os << "[ " << p.first << ", " << p.second << "]" ;
  41. }
  42.  
  43. ll P[1005][1005];
  44.  
  45. pair<ll,ll> dp[1005][1005];
  46.  
  47. int main(){
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(NULL);
  50.     //freopen("in.txt","r",stdin);
  51.     int n;
  52.     while(1){
  53.         cin>>n;
  54.         if(!n) return 0;
  55.         F0R(i,1,n+1)
  56.                 FOR(j,i) cin>>P[i][j];
  57.        
  58.         FOR(i,n+1) dp[n+1][i].fs = dp[n+1][i].snd =  dp[n+2][i].fs = dp[n+2][i].snd =  0;
  59.            
  60.        
  61.         for(int i=n; i>0; i--){
  62.             FOR(j,i){
  63.                 dp[i][j].fs = P[i][j];
  64.                 dp[i][j].fs = max(dp[i][j].fs, dp[i+1][j].fs  + dp[i+1][j+1].fs  - max(dp[i+2][j+1].fs,dp[i+2][j+1].snd) + P[i][j]);
  65.                 dp[i][j].fs = max(dp[i][j].fs, dp[i+1][j].fs  + dp[i+1][j+1].snd - (dp[i+2][j+1].fs > dp[i+2][j+1].snd ? dp[i+2][j+1].fs : dp[i+2][j+1].snd) + P[i][j]);
  66.                 dp[i][j].fs = max(dp[i][j].fs, dp[i+1][j].snd + dp[i+1][j+1].fs  - (dp[i+2][j+1].fs > dp[i+2][j+1].snd ? dp[i+2][j+1].fs : dp[i+2][j+1].snd) + P[i][j]);
  67.                 dp[i][j].fs = max(dp[i][j].fs, dp[i+1][j].snd + dp[i+1][j+1].snd - dp[i+2][j+1].snd + P[i][j]);
  68.                
  69.                
  70.                 //dp[i][j].fs = max(dp[i+1][j].fs, dp[i+1][j].snd) + max(dp[i+1][j+1].fs, dp[i+1][j+1].snd) + P[i][j] - max(dp[i+2][j+1].fs,dp[i+2][j+1].snd);
  71.                
  72.                
  73.                 dp[i][j].snd = dp[i+1][j].snd + dp[i+1][j+1].snd - dp[i+2][j+1].snd;
  74.             }
  75.         }
  76.        
  77.         cout<<max(dp[1][0].fs,dp[1][0].snd)<<endl;
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top