Submission

Score: 100

User: kimza

Problemset: จุดตัดบนกราฟ

Language: cpp

Time: 0.026 second

Submitted On: 2026-03-10 15:44:48

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9;

int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> v;
    vector<pair<int,int>> w;
    for(int i=0;i<n;i++){
        int a;
        cin >> a;
        v.push_back(a);
    }
    int i = 1;
    while(i<v.size()){
        int a = v[i-1];
        int b = v[i];
        //do process
        if(b>a){
            w.push_back({a,1});
            w.push_back({b,-1});
        }
        else{
            w.push_back({b,1});
            w.push_back({a,-1});
        }
        
        i++;
    }
    sort(w.begin(),w.end());
    // for(auto&x : w){
    //     cout << x.first << " " << x.second << "\n";
    // }
    int sum = 0;
    int max = -INF;
    for(int i=0;i<w.size();i++){
        sum+=w[i].second;
        if(sum>max) max = sum;
    }
    cout << max;
    return 0;
}