Submission #1378863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1378863		ziyad_alharbi	Art Exhibition (JOI18_art)	C++20	100 / 100	247 ms	47396 KiB

art

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<array<int,2>, null_type,less<array<int,2>>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    array<int,2>a[n];
    for(int x=0;x<n;x++)cin>>a[x][0]>>a[x][1];
    sort(a,a+n);
    int sm[n]={},vl[n]={},ans=LLONG_MIN;
    set<array<int,2>>st;
    for(int x=0;x<n;x++)
    {
        sm[x]=a[x][1];
        vl[x]=a[x][1]-a[x][0];
        if(x)
        {
            sm[x]+=sm[x-1];
            vl[x]+=vl[x-1]+a[x-1][0];
        }
        st.insert({vl[x],x});
    }
    for(int x=0;x<n;x++)
    {
        auto [s,i]=*st.rbegin();
        ans=max(ans,sm[i]-(x?sm[x-1]:0)-(a[i][0]-a[x][0]));
        st.erase({vl[x],x});
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

art.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main()
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50