제출 #1268329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268329		nadeshiko	Lasers (NOI19_lasers)	C++20	0 / 100	30 ms	7704 KiB

lasers

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

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

    ll L, R;
    if(!(cin >> L >> R)) return 0;

    vector<pair<ll,ll>> alwaysCoveredIntervals; // đoạn bị che mãi mãi (inclusive)

    for(int rr = 0; rr < R; ++rr){
        ll n; cin >> n;
        vector<ll> a(n);
        for(int i = 0; i < n; ++i) cin >> a[i];

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

        for(int i = 1; i <= n; ++i){
            ll x = pref[i];
            ll y = suff[i];
            if(x + y >= L){
                ll left = L - y;
                ll right = x;
                if(left < 1) left = 1;
                if(right > L) right = L;
                if(left <= right){
                    alwaysCoveredIntervals.emplace_back(left, right);
                }
            }
        }
    }

    if(alwaysCoveredIntervals.empty()){
        cout << 0 << '\n'; // không có vị trí bị che mãi mãi
        return 0;
    }

    sort(alwaysCoveredIntervals.begin(), alwaysCoveredIntervals.end());
    ll covered = 0;
    ll curL = alwaysCoveredIntervals[0].first;
    ll curR = alwaysCoveredIntervals[0].second;
    for(size_t i = 1; i < alwaysCoveredIntervals.size(); ++i){
        ll Ld = alwaysCoveredIntervals[i].first;
        ll Rd = alwaysCoveredIntervals[i].second;
        if(Ld > curR + 1){
            covered += (curR - curL + 1);
            curL = Ld; curR = Rd;
        } else {
            curR = max(curR, Rd);
        }
    }
    covered += (curR - curL + 1);

    if(covered > L) covered = L;
    cout << covered << '\n';
    return 0;
}

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