제출 #1318482

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318482		_unknown_2010	Art Exhibition (JOI18_art)	C++20	100 / 100	481 ms	55424 KiB

art

//#ifndef khos
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef khos
    #include "t_debug.cpp"
#else
    #define debug(...) 42
#endif
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using indexed_multiset = tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;

#define int int64_t
#define vi vector
#define ss second
#define ff first
#define TESTCASES
#define all(x) (x).begin(), (x).end()
const int mod = 1e9+7;
const int MAXN=2000000+5;
const int inf=1e18;

void solution() {
    int n;
    cin >> n;
    vi<int> a(n), b(n);
    vi<pair<int,int>> p;
    for(int i=0; i<n; i++){
        int x, y;
        cin >> x >> y;
        p.push_back({x, y});
    }
    sort(all(p));
    for(int i=0; i<n; i++)a[i]=p[i].ff, b[i]=p[i].ss;
    map<int,int> mp;
    for(int i=0; i<n; i++){
        mp[a[i]]+=b[i];
    }
    vi<int> vec;
    for(auto &[x, y]:mp){
        vec.push_back(x);
    }
    int l=0, sum=0, mx=0;
    for(int i=0; i<vec.size(); i++){
        sum+=mp[vec[i]];
        while(l!=i && vec[l+1]-vec[l]>mp[vec[l]]){
            sum-=mp[vec[l++]];
        }
        if(sum-vec[i]+vec[l]<mp[vec[i]])l=i, sum=mp[vec[i]];
        mx=max(mx, sum-vec[i]+vec[l]);
    }
    cout << mx;

/*

4 1
1 5
10 3
9 1
4 2
5 3
    

1 5
4 1
4 2
5 3
9 1
10 3

*/
}
int32_t main(){
    clock_t tStart = clock();
    #ifdef khos
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q = 1;
    #ifdef TESTCASES
        // cin >> q;
    #endif
    while(q--) {
        solution();
        cout << '\n';
    }
    cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}

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