Submission #1198775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198775		BigBadBully	Text editor (CEOI24_editor)	C++20	56 / 100	1247 ms	1114112 KiB

Main

#include <bits/stdc++.h>

#define pid pair<int,double>
#define pii pair<int,int>
#define ff first
#define ss second
const int inf = 1e18;
const int maxn = 1e3;
using namespace std;
void solve()
{
    int n;
    cin >> n;
    pii s,e;
    cin >> s.ff >> s.ss >> e.ff >> e.ss;
    s.ff--,s.ss--,e.ff--,e.ss--;
    vector<int> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    set<int> coord;
    coord.insert(s.ss);
    coord.insert(e.ss);
    for (int x : v)
        coord.insert(x);
    vector<int> vc;
    for (int x : coord)
        vc.push_back(x);
    map<int,int> cmps;
    for (int x : coord)
        cmps[x] = cmps.size();
    vector<vector<int>> d(n,vector<int>(coord.size(),inf));
    vector<vector<vector<array<int,3>>>> graph(n,vector<vector<array<int,3>>>(coord.size()));
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= cmps[v[i]]; j++)
        {
            if (i > 0)
                graph[i][j].push_back({i-1,min(j,cmps[v[i-1]]),1});
            if (i < n-1)
                graph[i][j].push_back({i+1,min(j,cmps[v[i+1]]),1});
            if (j > 0)
                graph[i][j].push_back({i,j-1,vc[j]-vc[j-1]});
            else if (i > 0)
                graph[i][j].push_back({i-1,cmps[v[i-1]],1});
            if (j < cmps[v[i]])
                graph[i][j].push_back({i,j+1,vc[j+1]-vc[j]});
            else if (i < n-1)
                graph[i][j].push_back({i+1,0,1});
        }
    d[s.ff][cmps[s.ss]] = 0;
    priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>> q;
    q.push({0,s.ff,cmps[s.ss]});
    while(q.size())
    {
        auto top = q.top();
        q.pop();
        int curd = d[top[1]][top[2]];
        if (curd != top[0])
            continue;
        for (auto a : graph[top[1]][top[2]])
            if (curd+a[2] < d[a[0]][a[1]])
                d[a[0]][a[1]] = curd+a[2],q.push({curd+a[2],a[0],a[1]});
    }
    cout << d[e.ff][cmps[e.ss]] << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    int t = 1;
    //cin >> t;
    while(t--)
    solve();
}

Compilation message (stderr)

Main.cpp:7:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    7 | const int inf = 1e18;
      |                 ^~~~

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