my code stock.com

Ball Stacking

Snippet options

Download: Download snippet as bcpp.cpp.
Copy snippet: For this you need a free my code stock.com account.
Embed code : You will find the embed code for this snippet at the end of the page, if you want to embed it into a website or a blog!

#include <bits/stdc++.h>
#define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
#define mk make_pair
#define pb push_back 
#define fi first
#define se second
const int INF = 0x3f3f3f3f;

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
const int N=1010;
int vec[N][N], n;
ll mx[2][N];


int main(){
        ios::sync_with_stdio(false);
	while(cin>>n) {
		if(!n)break;
		memset(mx,0,sizeof mx);
		for(int i=0;i<n;i++)
			for(int j=0;j<=i;j++)
				cin>>vec[j][i-j];

		int prv=0, curr=1;
		//mx[prv][0]=max(0,vec[0][0]);
		ll ans=0;

		for(int i=0;i<n;i++) {
			ll s=0;
			mx[curr][n-i]=-INF;
			for(int j=0;j<n-i;j++) {
				s+=vec[i][j];
				mx[curr][j]=mx[prv][j]+s;
			}
			for(int j=n-i-1;j>=0;j--) {
				mx[curr][j]=max(mx[curr][j], mx[curr][j+1]);
				ans=max(ans,mx[curr][j]);
			}
			swap(curr,prv);
		}
		cout<<ans<<'\n';
	}

        return 0;
}

Create a free my code stock.com account now.

my code stok.com is a free service, which allows you to save and manage code snippes of any kind and programming language. We provide many advantages for your daily work with code-snippets, also for your teamwork. Give it a try!

Find out more and register now

You can customize the height of iFrame-Codes as needed! You can find more infos in our API Reference for iframe Embeds.