제출 #1116899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116899		vjudge1	Art Exhibition (JOI18_art)	C++14	50 / 100	1053 ms	23760 KiB

art

#include <bits/stdc++.h>
#define sts(v) stable_sort(v.BE, v.E)
#define Rsts(v) stable_sort(v.rBE, v.rE)
#define rev(v) reverse(v.BE, v.E)
#define BE begin()
#define rBE rbegin()
#define E end()
#define rE rend()
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define F first
#define S second

using namespace std;
using ll = long long;

struct datos{
    ll ans, maxi, mini, suma; 
};

int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    int n; cin >> n;
    vector<pair<ll, ll>> v(n + 1);

    for(int i = 1; i <= n; i++){
        ll a, b; cin >> a >> b;

        v[i] = {a, b};
    }
    sts(v);
    vector<datos> ans(n + 1);
    ll ANS = 0;
    for(int i = 1; i <= n; i++){
        // F -> size, S -> val
        ans[i] = {
            v[i].S,
            v[i].F,
            v[i].F,
            v[i].S
        };
        for(int j = 1; j < i; j++){
            ll maxi = max(ans[j].maxi, v[i].F), mini = min(ans[j].mini, v[i].F),
               suma = ans[j].suma + v[i].S, res = suma - (maxi - mini);

            if(res > ans[i].ans)
                ans[i] = {
                    res,
                    maxi,
                    mini,
                    suma
                };
            ANS = max(ANS, ans[i].ans);
            
        }
        // cout << ans[i].ans << '\n';
    }

    cout << ANS << '\n';
	
    return 0;
}

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