Submission #1222483

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222483		khongphaifu	Art Exhibition (JOI18_art)	C++20	100 / 100	107 ms	12124 KiB

art

#include <bits/stdc++.h> 

using namespace std;

#define pb  push_back  
#define ll  long long
#define el  "\n"
#define alla(a,n)  a+1,a+n+1
#define fi first
#define se second
#define all(v)  v.begin(),v.end()
#define fu(i,a,b)  for(ll i=a;i<=b;i++)
#define fud(i,a,b)  for(ll i=a;i>=b;i--)

const ll MOD=1e9+7 ;//1234567891;
const ll inf=1e18;
const ll base = 311;
const ll N=1e6+5;
const ll N1=1e3+5;
template <class T> bool mini(T &x, T y){return (x > y ? x = y, 1 : 0);}
template <class T> bool maxi(T &x, T y){return (x < y ? x = y, 1 : 0);}
template <class T> void add(T &x, ll y){x += y; if(x >= MOD) x -= MOD;}
template <class T> void sub(T &x, T y){x -= y; if(x < 0) x += MOD;}
/*v*/
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1},
    dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};

void rtn()
{
    cerr<<el<<"time: "<<clock()<<"ms"<<el;
    exit(0);
}

ll n;
pair<ll,ll> art[N];

namespace sub1
{
    bool checksub()
    {
        return n<=5000;
    }

    void sol()
    {
        ll ans=0;
        fu(i,1,n)
        {
            ll S=0;
            fu(j,i,n)
            {
                S+=art[j].se;
                maxi(ans,S-art[j].fi+art[i].fi); 
            }
        }
        cout<<ans;  
    }
}

namespace sub2
{
    ll pre[N];
    void sol()
    {
        fud(i,n,1) pre[i]=pre[i+1]+art[i].se;
        ll mi=inf;
        ll ans=0;
        fud(i,n,1)
        {
            mini(mi,pre[i+1]+art[i].fi);
            maxi(ans,pre[i]+art[i].fi-mi);
        }
        cout<<ans;
    }
}

signed main(void)
{
    #define TASK  "art"
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);srand(time(0)); 
    if(fopen(TASK".inp","r"))
    {
        freopen(TASK".inp" ,"r",stdin) ; freopen(TASK".out" ,"w",stdout);
    }

    cin>>n;
    fu(i,1,n) cin>>art[i].fi>>art[i].se;
    sort(alla(art,n));
    if(sub1::checksub()) return sub1::sol(),0;
    return sub2::sol(),0;

    
    return 0;
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:83:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(TASK".inp" ,"r",stdin) ; freopen(TASK".out" ,"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
art.cpp:83:49: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         freopen(TASK".inp" ,"r",stdin) ; freopen(TASK".out" ,"w",stdout);
      |                                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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