Cod sursa(job #1889496)

Utilizator medicinedoctoralexandru medicinedoctor Data 22 februarie 2017 19:04:21
Problema Subsecventa de suma maxima Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <fstream>
#include <vector>

using namespace std;

long long s=-8223372036854775808,q,w;
vector <vector <int> > x;

ifstream cin ( "ssm.in");
ofstream cout("ssm.out");

void read()
{
	int n;
	
	cin >> n;
	x.resize(n);

	for (int i = 0; i < x.size(); i++)
	{
		x[i].resize(x.size());
		cin >> x[i][i] ;
		if (x[i][i] > s)
		{
			s = x[i][i];
			q = w = i ;
		}
	}
}

void solve()
{
	for (int i = 0; i < x.size(); i++)
		for (int j = i + 1; j < x.size(); j++ ) // x.size() == x[i].size() pentru orice 0 <= i < x.size()
		{
			x[i][j] = x[i][j-1] + x[j][j];
			if (x[i][j] > s)
			{
				s = x[i][j];
				q = i;
				w = j;
			}
		}
}

void write()
{
	cout << s << ' ' << q+1 << ' ' << w+1 ;
}

int main()
{
	read();

	solve();

	write();
	
	return 0;
}