Cod sursa(job #2032552)

Utilizator ruxandramateiMatei Ruxandra ruxandramatei Data 5 octombrie 2017 12:34:56
Problema Lupul Urias si Rau Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <iostream>
#include <fstream>
#define  DMAX  100010

using namespace std;

ifstream in("lupu.in");
ofstream out("lupu.out");

struct element{
    long lg;
    long lana;
}arrey[DMAX];

int N;
long M, K;//date de intrare
long long suma;
bool marcat[DMAX];

void citire(){
    in >> N >> M >> K;
    for(int i = 1; i<= N; i++){
        in >> arrey[i].lg >> arrey[i].lana;
    }
}

void rezolvare(){
    long maxim;
    int pozMin;
    bool ok;
    do{
        maxim = -1;
        pozMin = -1;
        ok = false;
        for(int i = 1; i <= N; i++){
            if(!marcat[i]  && (arrey[i].lg <= M) && (arrey[i].lg  > M - K) && maxim < arrey[i].lana){
                ok = true;
                maxim = arrey[i].lana;
                pozMin = i;
            }
        }
        if(!ok){
            long distDeparte = -1;
            for(int i = 1; i <= N; i++){
                if(!marcat[i] && arrey[i].lg > distDeparte && (arrey[i].lg <= M)){
                    maxim = arrey[i].lana;
                    distDeparte = arrey[i].lg;
                    pozMin = i;
                }
            }
        }
        if(pozMin != -1){
            suma += maxim;
            M -= K;
            marcat[pozMin] = true;
        }
    }while(pozMin != -1);

    out << suma;
}

int main(){
    citire();
    rezolvare();
    return 0;
}