Cod sursa(job #434635)
| Utilizator | Data | 6 aprilie 2010 12:46:36 | |
|---|---|---|---|
| Problema | Gutui | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | teme_upb | Marime | 0.66 kb |
#include<fstream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
#define Q 100001
#define y first
#define z second
bool c(pair<int,int>i,pair<int,int>j) {
return(i.z<j.z);
}
int main() {
int p[Q],n,h,u,i,j,k,s,v,m=0,t[Q];
ifstream f("gutui.in",ios::in);
ofstream g("gutui.out",ios::out);
vector<pair<int,int> > x;
f>>n>>h>>u;
for(i=0;i<n;i++) {
f>>j>>k;
x.push_back(make_pair(j,k));
}
sort(x.begin(),x.end(),c);
p[0]=-1;
for(i=n-1;i>=0;--i) {
s=1+(h-x[i].y)/u;
t[k=1]=s;
for(;p[s]&&s>0;t[++k]=s=p[s]);
if(s>0) {
v=(p[s-1]?p[s-1]:s-1);
for(j=1;j<=k;j++)
p[t[j]]=v;
m+=x[i].z;
}
}
g<<m;
return 0;
}
