Submission #1291647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291647		1ota	Airplane (NOI23_airplane)	C++20	22 / 100	49 ms	14388 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define entire(x) (x).begin(), (x).end()

const int inf = 9e18;

int32_t main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n, m; cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<vector<int>> adj(n);
    for (int i = 0; i < m; i++){
        int u, v; cin >> u >> v; u--, v--;
        adj[u].push_back(v); adj[v].push_back(u);
    }

    vector<int> suff(n, 0);
    for (int i = n-2; i > -1; i--) suff[i] = max(suff[i+1], a[i]); 

    int cur = 0, ans = 0;
    for (int i = 0; i < n-1; i++){
        if (suff[i+1] < cur) cur--, ans++;
        else if (cur < a[i+1]) {
            int delta = a[i+1] - cur;
            ans += delta; cur += delta;
        } else if (cur < suff[i+1]){
            cur++, ans++;
        } else ans++;
    } ans += cur;

    cout << ans << endl;

    return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 0 / 10
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37