Cod sursa(job #2823494)

Utilizator lolismekAlex Jerpelea lolismek Data 28 decembrie 2021 18:09:54
Problema Peste Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("peste.in");
ofstream fout("peste.out");

struct peste{
    int q, t; 
};

const int N = 50000 + 10;
peste v[N];

bool cmp(peste a, peste b){
    if(a.q != b.q) return a.q > b.q;
    return a.t < b.t;
}

int main(){
    int n, k, T;
    fin >> n >> k >> T;
    for(int i = 1; i <= n; i++) fin >> v[i].q >> v[i].t;
    sort(v + 1, v + n + 1, cmp);
    int t = 0, indice = 0, profit = 0;
    while(true){
        int maxi_timp = -1, p = 0;
        for(int i = 1; i <= k && i + indice <= n; i++) maxi_timp = max(maxi_timp, v[i + indice].t), p += v[i + indice].q;
        indice += k;
        t += maxi_timp;
        if(t <= T) profit += p;
        else break;
    }
    fout << profit;
    return 0;
}