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

换hash_map也超……

Posted by frkstyc at 2006-03-25 22:39:44 on Problem 2785
In Reply To:O(n^2)都tle, map也这么慢阿。 Posted by:first at 2006-03-25 21:17:42
> #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