| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贪心900+ms水过.....#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator