Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

O(n^2)都tle, map也这么慢阿。

Posted by first at 2006-03-25 21:17:42 on Problem 2785
#include <iostream>
#include <map>
using namespace std;

int N;
int num[4000][4];
map <int, int> sum[2];
int ans;
map<int, int>::iterator iter;
int  main()
{
	sum[0].clear();
	sum[1].clear();
	scanf("%d", &N);
	int i, j;
	for(i = 0; i < N; i ++)
      scanf("%d %d %d %d", &num[i][0], &num[i][1], &num[i][2], &num[i][3]);
    for(i = 0; i < N; i ++)
	 for(j = 0; j < N; j ++)
	 {
		 sum[0][num[i][0] + num[j][1]] ++;
         sum[1][num[i][2] + num[j][3]] ++;
	 }

    for(iter = sum[0].begin(); iter != sum[0].end(); iter ++)
	{
		ans += sum[1][-iter->first]*sum[0][iter->first];
	}
	printf("%d\n", ans);	
	return 0;   
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator