Submission #1286324

#TimeUsernameProblemLanguageResultExecution timeMemory
1286324juan_alejandroArt Exhibition (JOI18_art)C++20
100 / 100
126 ms8264 KiB
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#pragma GCC optimize("O2")
using namespace std;
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(0);
    cout<<fixed;
    int n;
    cin>>n;
    vector<pair<int,int>> x(n);
    for (int i = 0; i < n; i++)
    {
        cin>>x[i].first>>x[i].second;
    }
    sort(x.begin(),x.end());
    int res=0,mxv=-1e9,s=0;
    for (int i = 0; i < n; i++)
    {
        mxv=max(mxv,-s+x[i].first);
        res=max(res,s+x[i].second-x[i].first+mxv);
        s+=x[i].second;
    }
    cout<<res<<endl;/*
s:  3 5 2
d:  2 4 11

    3+2=
    5 10 13
    5 15 28

    3 8 10
    v+min d:2 -max d:i
    5 10 12
    3 6  1
    |
    v
    -min ->resprefijos sin contar min d
    5 8 3
                                  j-1
    ahora hallar sumado que Vj=-(∑s[i])+c[j] da mayor 
                      j-1         i=0
    o sea mayor: Vj=-(∑s[i])+c[j]
                      i=0  
  vc  1 4  -1
    V=2 1  4
    */
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...