Submission #1222402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222402		jakeob77	Text editor (CEOI24_editor)	C++17	14 / 100	1301 ms	372536 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ins insert
#define pb push_back
#define piii pair<int,pair<int,int>>
#define pii pair<int,int>

void solve(){
    int n;cin>>n;
    int st,stt,g,gg;cin>>st>>stt>>g>>gg;
    vector<int>a(n);
    for(int &d:a) cin>>d;
    vector<vector<vector<pii>>>adj(n+1,vector<vector<pii>>(5003));

    for(int i=1;i<=n;i++){
        for(int j=1;j<=a[i-1]+1;j++){
            if(i!=1&&j==1){
                adj[i][j].pb({i-1,a[i-2]+1});
            }
            if(i!=n&&j==a[i-1]+1){
                adj[i][j].pb({i+1,1});
            }
            if(j>1){
                adj[i][j].pb({i,j-1});
            }
            if(j<a[i-1]+1){
                adj[i][j].pb({i,j+1});
            }
            if(i>1){
                adj[i][j].pb({i-1,min(j,a[i-2]+1)});
                
            }
            if(i<n){
                adj[i][j].pb({i+1,min(j,a[i]+1)});
            }
        }
    }
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=a[i-1]+1;j++){
            for(auto el:adj[i][j]){
                cout<<el.first<<'/'<<el.second<<' ';
            }
            cout<<endl;
        }
        cout<<endl;
    }*/
    
    vector<vector<int>>dist(n+1,vector<int>(5003,int(1e9+2e6)));
    priority_queue<piii,vector<piii>,greater<piii>>pq;
    dist[st][stt]=0;
    pq.push({0,{st,stt}});
    while(pq.size()){
        const auto [d,p]=pq.top();pq.pop();
        //cout<<p.first<<'/'<<p.second<<endl;
        if(d!=dist[p.first][p.second]) continue;
        if(p.first==g&&p.second==gg) break;
        for(auto ne:adj[p.first][p.second]){
            if(d+1<dist[ne.first][ne.second]){
                dist[ne.first][ne.second]=d+1;
                //cout<<"next:"<<ne.first<<' '<<ne.second<<' '<<d<<endl;
                pq.push({d+1,{ne.first,ne.second}});
            }
        }
    }
    cout<<dist[g][gg]<<endl;
}

int main() {
	int t=1;
    while(t--)solve();
}

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