Cod sursa(job #751332)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 25 mai 2012 18:16:44
Problema P-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<stdio.h>
#include<algorithm>

#define maxn 2005

using namespace std;

FILE*f=fopen("psir.in","r");
FILE*g=fopen("psir.out","w");

int n,nr;
int v[maxn],N[maxn];
unsigned int D[maxn][maxn];

inline int cb ( int val ){
	int p = 1,m,u = nr;
	
	while ( p <= u ){
		m = (p + u)>>1;
		if ( N[m] == val )	return m;
		if ( N[m] > val )	u = m - 1;
		else	p = m + 1;
	}
	
	return 0;
}

int main () {
	
	fscanf(f,"%d",&n);
	for ( int i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d,",&v[i]); N[i] = v[i];
	}
	
	sort(N+1,N+n+1);
	for ( int i = 1 ; i <= n ; ++i ){
		if ( N[i] != N[i-1] ){
			N[++nr] = N[i];
		}
	}
	
	for ( int i = 1 ; i <= n ; ++i ){
		v[i] = cb(v[i]);
	}
	
	unsigned int sol = 0;
	for ( int i = 2 ; i <= n ; ++i ){
		for ( int j = 1 ; j < i ; ++j ){
			
			unsigned int now = 1;
			if ( v[i] > v[j] ){
				now += D[j][nr] - D[j][v[i]];
			}
			else{
				if ( v[i] < v[j] ){
					now += D[j][v[i]-1];
				}
			}
			
			D[i][v[j]] += now;
			sol += now;
		}
		
		for ( int j = 2 ; j <= nr ; ++j ){
			D[i][j] += D[i][j-1];
		}
	}
	
	fprintf(g,"%u\n",sol);
	
	fclose(f);
	fclose(g);
	
	return 0;
}