제출 #1316174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316174		1ota	Lasers (NOI19_lasers)	C++20	100 / 100	223 ms	60548 KiB

lasers

#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()

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

    int m, n; cin >> m >> n; // m = row size
    vector<vector<int>> row(n);
    
    for (int i = 0; i < n; i++){
        int x; cin >> x;
        for (int j = 0, w; j < x; j++) cin >> w, row[i].push_back(w);
    }

    // only the regions with interval depth n will survive
    // start === {coord, 1}, end === {coord, -1} // [start, end)
    vector<pii> safe;

    auto solve = [&](vector<int> a){
        int nr = (int) a.size();
        int bef = 0, aft = accumulate(entire(a), 0ll);
        safe.push_back(pii{0, 1}); safe.push_back(pii{m - aft, -1});
        int pos = m - aft;
        for (int i = 0; i < nr; i++){
            bef += a[i]; aft -= a[i];
            pos = max(pos, bef);
            safe.push_back(pii{pos, 1});
            pos = m - aft;
            safe.push_back(pii{pos, -1});
        }
    };

    for (auto a : row) solve(a);
    sort(entire(safe));

    int depth = 0, last = 0, ans = 0;
    for (auto [pos, type] : safe){
        if (type == 1) { depth++, last = pos; continue; }
        if (type == -1) {
            if (depth == n) ans += pos - last;
            last = pos; depth--;
        }
    }

    cout << m - ans << endl;

    return 0;
}

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