Submission #1220435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220435		KindaGoodGames	Text editor (CEOI24_editor)	C++20	5 / 100	4064 ms	394592 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int,int>
#define tiii tuple<int,int,int>

int INF = numeric_limits<int>::max()/2;

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    int sr, sc;
    int er, ec;
    
    cin >> n;
    cin >> sr >> sc;
    cin >> er >> ec;

    sr--;sc--;
    er--;ec--;

    vector<int> arr(n);

    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    
    set<int> important;

    for(int i = 0; i < n; i++){
        important.insert(arr[i]);
    }
    important.insert(sc);
    important.insert(ec);
    important.insert(INF);
    important.insert(-INF);

    vector<int> pos(important.begin(),important.end()); 
    map<int,int> toInd;
    for(int i = 0; i < pos.size(); i++){
        toInd[pos[i]] = i;
    }
     
    priority_queue<tiii,vector<tiii>, greater<tiii>> pq; 
    vector<vector<int>> dist(n,vector<int>(pos.size(), INF));

 
    pq.push({0,sr,sc});

    int iter = 0;
    while(pq.size()){
        int d,r,c;
        tie(d,r,c) = pq.top(); pq.pop();
 
        if(dist[r][toInd[c]] < d) continue;
        dist[r][toInd[c]] = d;

        if(r == er && ec == c) break;
        
        int nxt = *upper_bound(pos.begin(),pos.end(), c);
        auto it =  lower_bound(pos.begin(),pos.end(), c);
        int prev =-INF; 
        if(it != pos.begin()){ 
            it--;
            prev= *it;
        }else{
            prev = -INF;
        }

        // horizontal
        if(prev >= 0) pq.push({abs(c-prev)+d,r,prev});
        else if(r-1 >= 0){
            pq.push({d+1,r-1,arr[r-1]});
        }
        if(nxt <= arr[r]) pq.push({abs(c-nxt)+d,r,nxt});
        else if(r+1 < n){
             pq.push({d+1,r+1,0});  
        }

        // vertical 
        if(r > 0) pq.push({d+1,r-1,min(c,arr[r-1])}); 
        if(r+1 < n) pq.push({d+1,r+1,min(c,arr[r+1])}); 
    }

    cout << dist[er][toInd[ec]] << endl;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 26
• Subtask 4: 0 / 11
• Subtask 5: 0 / 44