Pagini recente » Cod sursa (job #342011) | Cod sursa (job #715559) | Cod sursa (job #780971) | Cod sursa (job #1740279) | Cod sursa (job #438143)
Cod sursa(job #438143)
#include <iostream>
#include <fstream>
#include <stdlib.h>
using namespace std;
typedef struct gs{
unsigned int ng;
unsigned int gg;
} gs;
unsigned int h,u;
unsigned int n;
gs *gt;
unsigned int *luate;
unsigned int *q /* cate mai pot lua de pe niv. respectiv */;
unsigned int nr_luate = 0;
unsigned int p;
unsigned int gmax = 0;
unsigned int nivmax = 0;
unsigned int nivmin = UINT_MAX;
int compare (const void * a, const void * b)
{
if( ((gs *)b)->gg != ((gs *)a)->gg ){
if ( ((gs *)b)->gg > ((gs *)a)->gg ){
return 1;
}
else{
return -1;
}
}
else{
if( ((gs *)b)->ng > ((gs *)a)->ng ){
return 1;
}
else
if ( ((gs *)b)->ng < ((gs *)a)->ng ){
return -1;
}
else{
return 0;
}
}
}
int get_gmax(){
//cout<<"nivmax = "<<nivmax<<", nivmin = "<<nivmin<<", p = "<<p<<", n = "<<n<<endl;
//unsigned int j, barrier;
unsigned int i, j, k, t, y, flag, barrier;
//barrier = nivmax + 1;
for(i=0;i<p;i++){
//cout<<nr_luate<<endl;
/*
for(j=0;j<nr_luate;j++){
cout<<"q[j] = "<<q[j]<<", ";
}
cout<<endl;*/
if(i==n){
break;
}
k = 0;
t = 0;
y = 0;
flag = 1;
for(j=0;j<nr_luate;j++){
if(luate[j] > gt[i].ng){
k++; /* cate s-au luat de "mai sus" */
//if(q[j]>0){
//q[j]--;
//}
}
else {
if(luate[j] < gt[i].ng){
t++; /* cate s-au luat de "mai jos" */
if(q[j] == 0){
flag = 0;
}
//if(q[j]>0){
//q[j]--;
//}
}
else{ /* cele luate de pe nivelul curent */
y++;
if(q[j] == 0){
flag = 0;
}
}
}
}
/*
TODO:
-nu pot lua elementul curent daca am luat deja alte elemente care se afla "mai jos" ca el,
consumandu-i astfel pozitia
*/
//cout<<"nivmax = "<<nivmax<<", gt.ng = "<<gt[i].ng<<", gt.gg = "<<gt[i].gg<<", k = "<<k<<endl;
if( ( nivmax + 1 > ( k + y) + gt[i].ng ) && flag && ( gt[i].ng < barrier ) ){
//if(nivmax - gt[i].ng - k > 0 ){ //????
luate[nr_luate] = gt[i].ng;
//cout<<nr_luate<<" "<<nivmax + 1 - gt[i].ng<<endl;
if( nivmax + 1 < gt[i].ng + ( k + y) ){
q[nr_luate] = 0;
}
else{
q[nr_luate] = nivmax + 1 - gt[i].ng - ( k + y);
}
//cout<<"--- q = "<<q[nr_luate]<<", k = "<<k<<", y = "<<y<<", ng = "<<gt[i].ng<<endl;
nr_luate++;
for(j=0;j<nr_luate;j++){
if( gt[i].ng >= luate[j] )
if(q[j]>0){
q[j]--;
}
}
//cout<<nr_luate<<" "<<gt[i].gg<<" "<<gt[i].ng<<endl;
gmax = gmax + gt[i].gg;
//cout<<"q = "<<q[nr_luate - 1]<<", ng = "<<gt[i].ng<<", g = "<<gt[i].gg<<", k = "<<k<<", nivmax = "<<nivmax<<", n_luate = "<<nr_luate<<endl;
if( nivmax == ( k + y ) + gt[i].ng ){ //nu mai pot lua nimic de pe acel nivel
if( gt[i].ng < barrier )
barrier = gt[i].ng;
//cout<<"barrier = "<<barrier<<endl;
}
//cout <<" "<< nivmax + 1 - gt[i].ng - k <<endl;
}
else{
p++;
}
}
return 0;
}
int read_vec(){
ifstream fin;
unsigned int i, j;
//int nvc;
unsigned int hg;
int f = 1;
int o;
fin.open("gutui.in",ios::in);
fin>>n;
fin>>h;
fin>>u;
o = u - ( h % u ) - 1;
h = h + o;
gt = (gs *)malloc( n * sizeof( gs ));
nivmax = h / u;
for(i=0;i<n;i++){
fin>>hg;
fin>>gt[i].gg;
if(hg>h){
i--;
n--;
continue;
}
hg = hg + o;
gt[i].ng = hg / u;
if(gt[i].ng < nivmin){
nivmin = gt[i].ng;
}
}
p = nivmax - nivmin + 1;
if(p > n){ //??
p = n;
}
luate = (unsigned int *)malloc( p * sizeof( unsigned int ));
q = (unsigned int *)malloc( p * sizeof( unsigned int ));
qsort (gt, n, sizeof(gs), compare);
fin.close();
return 0;
}
int write_sol(){
ofstream fout;
fout.open("gutui.out",ios::out);
fout<<gmax;
fout.close();
return 0;
}
int main(){
read_vec();
get_gmax();
write_sol();
//cin.get();//to_comment
return 0;
}