Cod sursa(job #3249946)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 18 octombrie 2024 19:30:44
Problema Orase Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
//#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;

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

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m, n; in >> m >> n;
    pair<int, int> v[n + 1];
    for(int i = 1; i <= n; i++){
        in >> v[i].first >> v[i].second;
    }

    v[0] = make_pair(0, 0);
    sort(v + 0, v + n + 1);

    int d[n + 1];
    int l[n + 1];

    for(int i = 0; i <= n; i++){
        d[i] = v[i].first;
        l[i] = v[i].second;
    }

    int sol = 0;
    int dp[n + 1];
    for(int i = 0; i <= n; i++) dp[i] = 0;
    for(int i = 1; i <= n; i++){
        dp[i] = dp[i - 1] + (d[i] - d[i - 1]);
        sol = max(sol, dp[i] + l[i]);
        dp[i] = max(dp[i], l[i]);

        if(i > 1 && d[i] == d[i - 1]) sol = max(sol, l[i] + l[i - 1]);
    }

    out << sol << '\n';

    return 0;
}