Submission #8328549


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<ll> x(m);
    for (int i = 0; i < m; i++) {
        cin >> x[i];
        x[i]--;
    }

    auto check = [&](ll ans) {
        ll pos = 0;
        for (int i = 0; i < m; i++) {
            ll L = x[i] - min(pos, x[i]);
            if (ans < L) return false;
            ll R = max(ans - 2 * L, (ans - L) / 2);
            if (R < 0) return false;
            pos = max(pos, x[i] + R + 1);
        }
        return pos >= n;
    };

    ll ng = -1, ok = 2 * n;
    while (ok - ng > 1) {
        ll mid = (ok + ng) / 2;
        (check(mid) ? ok : ng) = mid;
    }
    cout << ok << "\n";
    return 0;
}

Submission Info

Submission Time
Task D - 壊れた電車
User octo
Language C++14 (GCC 5.4.1)
Score 100
Code Size 814 Byte
Status AC
Exec Time 24 ms
Memory 1024 KB

Judge Result

Set Name Sample Dataset1 Dataset2 Dataset3
Score / Max Score 0 / 0 20 / 20 60 / 60 20 / 20
Status
AC × 2
AC × 17
AC × 36
AC × 60
Set Name Test Cases
Sample sample-01.txt, sample-02.txt
Dataset1 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt
Dataset2 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt
Dataset3 sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, 03-21.txt, 03-22.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt AC 1 ms 256 KB
01-02.txt AC 1 ms 256 KB
01-03.txt AC 1 ms 256 KB
01-04.txt AC 1 ms 256 KB
01-05.txt AC 1 ms 256 KB
01-06.txt AC 1 ms 256 KB
01-07.txt AC 1 ms 256 KB
01-08.txt AC 1 ms 256 KB
01-09.txt AC 1 ms 256 KB
01-10.txt AC 1 ms 256 KB
01-11.txt AC 1 ms 256 KB
01-12.txt AC 1 ms 256 KB
01-13.txt AC 1 ms 256 KB
01-14.txt AC 1 ms 256 KB
01-15.txt AC 1 ms 256 KB
02-01.txt AC 1 ms 256 KB
02-02.txt AC 1 ms 256 KB
02-03.txt AC 1 ms 256 KB
02-04.txt AC 2 ms 384 KB
02-05.txt AC 18 ms 1024 KB
02-06.txt AC 9 ms 640 KB
02-07.txt AC 17 ms 1024 KB
02-08.txt AC 17 ms 1024 KB
02-09.txt AC 17 ms 1024 KB
02-10.txt AC 1 ms 256 KB
02-11.txt AC 18 ms 1024 KB
02-12.txt AC 18 ms 1024 KB
02-13.txt AC 16 ms 1024 KB
02-14.txt AC 18 ms 1024 KB
02-15.txt AC 14 ms 1024 KB
02-16.txt AC 16 ms 1024 KB
02-17.txt AC 18 ms 1024 KB
02-18.txt AC 18 ms 1024 KB
02-19.txt AC 17 ms 1024 KB
03-01.txt AC 1 ms 256 KB
03-02.txt AC 1 ms 256 KB
03-03.txt AC 1 ms 256 KB
03-04.txt AC 24 ms 1024 KB
03-05.txt AC 8 ms 512 KB
03-06.txt AC 11 ms 640 KB
03-07.txt AC 19 ms 1024 KB
03-08.txt AC 20 ms 896 KB
03-09.txt AC 1 ms 256 KB
03-10.txt AC 22 ms 1024 KB
03-11.txt AC 22 ms 1024 KB
03-12.txt AC 8 ms 512 KB
03-13.txt AC 21 ms 1024 KB
03-14.txt AC 20 ms 1024 KB
03-15.txt AC 24 ms 1024 KB
03-16.txt AC 15 ms 1024 KB
03-17.txt AC 20 ms 1024 KB
03-18.txt AC 22 ms 1024 KB
03-19.txt AC 22 ms 1024 KB
03-20.txt AC 22 ms 1024 KB
03-21.txt AC 22 ms 1024 KB
03-22.txt AC 22 ms 1024 KB
sample-01.txt AC 1 ms 256 KB
sample-02.txt AC 1 ms 256 KB