Submission #1345168

#TimeUsernameProblemLanguageResultExecution timeMemory
1345168po_rag526Art Exhibition (JOI18_art)C++17
100 / 100
106 ms15948 KiB
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"
#define AI ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
struct pr
{
    ll a;
    ll b;
};
bool comp(pr&x,pr&y)
{
    if(x.a==y.a)
    return x.b<y.b;
    return x.a<y.a;
}
int main()
{
    AI
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ll n,i,j;
    cin>>n;
    vector<pr>v(n);
    for(i=0;i<n;i++)
    cin>>v[i].a>>v[i].b;
    ll ans=0;
    sort(v.begin(),v.end(),comp);
    vector<ll>p(n+1,0);
    p[0]=0;
    for(i=1;i<=n;i++)
    p[i]=p[i-1]+v[i-1].b;
    ans=0;
    ll mij=0;
    ll dp[n];
    dp[0]=v[0].b;
    ans=max(ans,dp[0]);
    for(i=1;i<n;i++)
    {
        dp[i]=max(v[i].b,dp[i-1]+v[i].b-(v[i].a-v[i-1].a));
        ans=max(dp[i],ans);
    }
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...