Cod sursa(job #3142758)

Utilizator ecaterinaEcaterina Stefanescu ecaterina Data 24 iulie 2023 12:01:52
Problema Lupul Urias si Rau Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

#define NMAX 100001

int pas[NMAX];
int c[NMAX];

int v[NMAX];

void qsortpas(int begin, int end) {
    int b, e, pivot, aux;
    
    b = begin;
    e = end;
    pivot = pas[(e+b)/2];
    
    while (pas[b]<pivot) {
        b++;
    }
    while (pas[e]>pivot) {
        e--;
    }
    while (b<e) {
        swap(pas[b], pas[e]);
        swap(c[b], c[e]);
        do {
            b++;
        } while (pas[b]<pivot);
        do {
            e--;
        } while (pas[e]>pivot);
    }
    if (begin < e) {
        qsortpas(begin, e);
    }
    if (e+1 < end) {
        qsortpas(e+1, end);
    }
}

void qsortc(int begin, int end) {
    int b, e, pivot, aux;
    
    b = begin;
    e = end;
    pivot = c[(e+b)/2];
    
    while (c[b]>pivot) {
        b++;
    }
    while (c[e]<pivot) {
        e--;
    }
    while (b<e) {
        swap(c[b], c[e]);
        do {
            b++;
        } while (c[b]>pivot);
        do {
            e--;
        } while (c[e]<pivot);
    }
    if (begin < e) {
        qsortc(begin, e);
    }
    if (e+1 < end) {
        qsortc(e+1, end);
    }
}

void myqsort(int begin, int end) {
    int b, e, pivot, aux;
    
    b = begin;
    e = end;
    pivot = v[(e+b)/2];
    
    while (v[b]>pivot) {
        b++;
    }
    while (v[e]<pivot) {
        e--;
    }
    while (b<e) {
        swap(v[b], v[e]);
        do {
            b++;
        } while (v[b]>pivot);
        do {
            e--;
        } while (v[e]<pivot);
    }
    if (begin < e) {
        qsortc(begin, e);
    }
    if (e+1 < end) {
        qsortc(e+1, end);
    }
}

int main() {
    FILE *fin, *fout;
    fin = fopen("lupu.in", "r");
    fout = fopen("lupu.out", "w");
    
    int n, x, l, i, start, end, nr, j;
    long long int sum;
    
    fscanf(fin, "%d%d%d", &n, &x, &l);
    for (i=0; i<n; i++) {
        fscanf(fin, "%d%d", &pas[i], &c[i]);
        pas[i] = l+2-(pas[i]+l-1)/l;
    }
    
    qsortpas(0, n-1);
    
    for (i=0; i<n; i++) {
        start = i;
        end = i+1;
        while (end<n && pas[start]==pas[end]) {
            end++;
        }
        qsortc(start, end-1);
    }
    
//    for (i=0; i<n; i++) {
//        fprintf(fout, "%d %d\n", pas[i], c[i]);
//    }
    
    i=0;
    nr = 0;
    while (i<n) {
        j=0;
        while (pas[i]==pas[i+j] && i+j<n && j<pas[i]) {
            v[nr] = c[i+j];
            nr++;
            j++;
        }
        i+=j-1;
        if (j<=pas[i]) {
            j=i;
            while (pas[j]==pas[i] && i<n) {
                i++;
            }
        } else {
            i++;
        }
    }
    
    myqsort(0, nr-1);
    
    sum = 0;
    for (i=0; i<pas[n-1]; i++) {
        sum+=(long long)v[i];
    }
    fprintf(fout, "%lld", sum);
    
    
    fclose(fin);
    fclose(fout);
    return 0;
}