Cod sursa(job #1053548)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 12 decembrie 2013 20:17:40
Problema Matrice 2 Scor 0
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.39 kb
#include<fstream>
using namespace std;
int n,m,A,R[30100],C[30100],sol,nsol;

inline void Solve(int P,int Q)
{
	if(P>n || Q>m)
		return;
	int maxim=0,nmaxim=0,minim=30100,nminim=0,rez;
	int i,now=0;
	for(i=1;i<Q;i++)
		now+=C[i];
	for(i=Q;i<=m;i++)
	{
		now+=C[i];
		now-=C[i-Q];
		if(now>maxim)
		{
			maxim=now;
			nmaxim=1;
		}
		else
			if(now==maxim)
				nmaxim++;
		if(now<minim)
		{
			minim=now;
			nminim=1;
		}
		else
			if(now==minim)
				nminim++;
	}
	now=0;
	for(i=1;i<P;i++)
		now+=R[i];
	for(i=P;i<=n;i++)
	{
		now+=R[i];
		now-=R[i-P];
		if(2*now-P>0)
		{
			rez=now*maxim+(P-now)*(Q-maxim);
			if(rez>sol)
			{
				sol=rez;
				nsol=nmaxim;
			}
			else
				if(rez==sol)
					nsol+=nmaxim;
		}
		else
		{
			if(2*now-P<0)
			{
				rez=now*minim+(P-now)*(Q-minim);
				if(rez>sol)
				{
					sol=rez;
					nsol=nminim;
				}
				else
					if(rez==sol)
						nsol+=nminim;
			}
			else
			{
				rez=now*Q;
				if(rez>sol)
				{
					sol=rez;
					nsol=m-Q+1;
				}
				else
					if(rez==sol)
						nsol+=m-Q+1;
			}
		}
	}
}

int main()
{
	int i;
	ifstream fin("matrice.in");
	fin>>n>>m>>A;
	for(i=1;i<=n;i++)
		fin>>R[i];
	for(i=1;i<=m;i++)
		fin>>C[i];
	fin.close();
	
	for(i=1;i<=A;i++)
		if(A%i==0)
			Solve(i,A/i);
		
	ofstream fout("matrice.out");
	fout<<sol<<' '<<nsol<<"\n";
	fout.close();
	return 0;
}