Cod sursa(job #2823941)

Utilizator puica2018Puica Andrei puica2018 Data 30 decembrie 2021 11:43:48
Problema Stergeri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

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

/// f(i,j) = valoarea de la poz.i dupa j operatii
/// f(k,0) = k
/// f(k,m) = f(x,m-1)+x-k, m>=1
/// daca k>=st[m]: x=k+dr[m]-st[m]+1
/// altfel: x=k

/// daca k>=st[m]
///    f(k,m) = f(k+l[m],m-1)
/// altfel
///    f(k,m) = f(k,m-1)

int n,m,k;
int st[100005],dr[100005];

/*
int f(int k,int m)
{
    if(m==0)
        return k;
    if(k>=st[m])
        return f(k+dr[m]-st[m]+1,m-1);
    return f(k,m-1);
}
*/

int main()
{
    fin>>n>>m>>k;
    int i;
    for(i=1; i<=m; i++)
        fin>>st[i]>>dr[i];
    int sum=k;
    for(i=m; i>=1; i--)
    {
        if(sum>=st[i])
            sum+=dr[i]-st[i]+1;
    }
    fout<<sum<<"\n";
    return 0;
}