Cod sursa(job #2071373)

Utilizator Valentin0709Datcu George Valentin Valentin0709 Data 20 noiembrie 2017 17:13:27
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

FILE*f=fopen("heavymetal.in","r");
FILE*g=fopen("heavymetal.out","w");

long long n,tmx,t,b[100005];

struct formatie {
    int t1,t2;
} a[100005];

int comp(formatie a,formatie b) {
    return a.t2<b.t2||(a.t2==b.t2&&a.t1>b.t1);
}

void citire() {
    int i;

    fscanf(f,"%lld",&n);
    for(i=1;i<=n;i++) fscanf(f,"%d%d",&a[i].t1,&a[i].t2);

}

int verif() {
    int i,j;

    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
        if(b[j]&&b[i]&&min(a[i].t2,a[j].t2)>max(a[i].t1,a[j].t1)) return 0;
    return 1;
}

void bkt(int k) {
    int i,j;

    for(i=0;i<=1;i++) {
        b[k]=i;
        if(k==n) {
            if(verif()) {
                t=0;
                for(j=1;j<=n;j++) t+=b[j]*(a[j].t2-a[j].t1);
                if(t>tmx) tmx=t;
            }
        }
        else bkt(k+1);
    }

}

int main() {

    citire();
    bkt(1);

    fprintf(g,"%lld",tmx);

    fclose(f); fclose(g);

    return 0;
}