Submission #1132256

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132256		fcmalkcin	Lasers (NOI19_lasers)	C++20	100 / 100	591 ms	35280 KiB

lasers

// Online C++ compiler to run C++ program online
#include<bits/stdc++.h> // header for every library
using namespace std;
#define ll int
const ll maxn = 5e5 + 10;

map<int, int> prefCover; 
ll vt[maxn]; 

int main() {

    ll n, l; 
    cin >> l >> n; 
    for (int i = 1; i <= n; i++) {
        ll siz; 
        cin >> siz; 
        int total = 0; 
        for (int j = 0; j < siz; j++) {
            cin >> vt[j];
            total += vt[j];
        }
        int cur = 0;
        for (int j = 0; j <= siz; j++) {
            // range: cur -> min(L - (total - cur), cur + vt[j])
            ll end = l; 
            if (j < siz) end = min(l - (total - cur), cur + vt[j]); 
            if (cur <= end) {
                prefCover[cur]++; 
                prefCover[end]--;
            }
            if (j != siz) {
                cur += vt[j];
            }
        }
    }
    ll ans = 0; 
    int prev = 0; 
    int cntnw = 0;
    for (auto p: prefCover) {
        int cur = p.first; 
        if (cntnw == n) {
            ans += (cur - prev);
        }
        cntnw += p.second; 
        prev = cur; 
    }
    cout << l - ans << endl; 
}

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