제출 #1271783

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271783		cbnk32_tuandung	Lasers (NOI19_lasers)	C++20	24 / 100	78 ms	27460 KiB

lasers

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

/*
run
 g++ LASER.cpp -std=c++1y -o run.exe && ./run.exe
*/

// CONSTANTs

constexpr int MAX_N = 500000 + 5;

// GIVEN

int N, L;
vector<int> A[MAX_N];

// VARIABLEs

int x, y;

// FUNCTIONs

// SUBTASKs

bool checkSub2 = true;

namespace sub1 {
    bool checkInput() {
        return (checkSub2 && (N == 1));
    }
    int solve() {
        cout << max(0ll, 1ll * A[1][0] + A[1][0] - L);
        return 0;
    }
}

namespace sub2 {
    bool checkInput() {
        return (checkSub2);
    }
    int solve() {
        int maxX = A[1][0];
        for (int i = 2; i <= N; ++i) maxX = max(maxX, A[i][0]);
        cout << max(0ll, 1ll * maxX + maxX - L);
        return 0;
    }
}

namespace TRAU {
    bool blocked[MAX_N << 1];
    int solve() {
        for (int i = 1; i <= N; ++i) {
            long long sum = 0;
            for (int j : A[i]) sum += j;
            long long pre = A[i][0];
            sum -= A[i][0];
            if ((A[i][0] * 2) > (L - sum)) {
                int lo = max(1ll, L - sum - A[i][0] + 1);
                int hi = min(L, A[i][0]);
                for (int j = lo; j <= hi; ++j) blocked[j] = true;
            }
            for (int j = 1; j < A[i].size(); ++j) {
                sum -= A[i][j];
                if ((A[i][j] * 2) > (L - sum - pre)) {
                    int lo = max(1ll, L - sum - A[i][j]);
                    int hi = min(1ll * L, A[i][j] + pre);
                    for (int k = lo; k <= hi; ++k) blocked[k] = true;
                }
                pre += A[i][j];
            }
        }
        int res = 0;
        for (int i = 1; i <= L; ++i) res += blocked[i];
        cout << res;
        return 0;
    }
}

// MAIN

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    // freopen("LASERS.INP", "r", stdin);
    // freopen("LASERS.OUT", "w", stdout);

    cin >> L >> N;
    for (int i = 1; i <= N; ++i) {
        cin >> x;
        if (x > 1) {
            checkSub2 = false;
        }
        while (x--) {
            cin >> y;
            A[i].push_back(y);
        }
    }

    if (sub1::checkInput()) return sub1::solve();
    if (sub2::checkInput()) return sub2::solve();
    TRAU::solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 21
• Subtask 5: 0 / 22
• Subtask 6: 0 / 13