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

贪心900+ms水过.....

Posted by crazyX at 2016-03-11 20:02:19 on Problem 2393
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define INT_MAX 1<<30
using namespace std;
typedef long long ll;
const int INF=0x7F;
const int maxn=10000+7;
int n,s;
struct fuck{
	ll c,y;
	
	int rep;
	ll gain;
}F[maxn];
ll temp,ans;
int main()
{
	scanf("%d%d",&n,&s);
	for (int i = 0; i < n; i += 1)
	{
		scanf("%d%d",&F[i].c,&F[i].y);
		F[i].rep=i;
	}
	for (int i = 0; i < n; i += 1)
	{
		for (int j = i+1; j < n; j += 1)
		{
			temp=(F[j].c-F[i].c)-(j-i)*s;
			if(temp>0&&F[j].gain<temp){
				F[j].rep=i;
				F[j].gain=temp;
			}
		}
	}
	for (int i = 0; i < n; i += 1)
	{
		if (F[i].rep==i)
		{
			ans+=F[i].y*F[i].c;
		}else{
			ans+=F[F[i].rep].c*F[i].y;
			ans+=(i-F[i].rep)*F[i].y*s;
		}
	}
	printf("%I64d\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