Submission #1156888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156888		Owen11	Lasers (NOI19_lasers)	C++20	100 / 100	69 ms	9412 KiB

lasers

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

# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"

const int cnst = 2e5+5;
bool mutipletestcase = 0;
//bool debug = false;

bool sorting(pair<int, int> a, pair<int, int> b) {
    return a.sec > b.sec;
}

void solve() {
    int n, q; cin >> n >> q;

    int ans = 0;
    vector<pair<int, int>> range;

    while(q--) {
        // cerr << "IN" << endl;
        int x; cin >> x;
        int num[x+5];
        int pre[x+5]; pre[0] = 0;
        int suf[x+5]; suf[x+1] = n+1;
        for(int i = 1; i<=x; i++) {
            cin >> num[i];
            pre[i] = pre[i-1]+num[i]; 
        }

        int prev = 0;
        for(int i = x; i>=1; i--) suf[i] = suf[i+1]-num[i];

        for(int i = 1; i<=x; i++) {
            if(suf[i] <= pre[i]) range.pb({suf[i], pre[i]});
        }
    }

    sort(range.begin(), range.end(), sorting);

    int l = n+2; int r = n+1;
    for(auto v: range) {
        // cerr << v.fir << " " << v.sec << endl;
        if(v.sec < l) {
            ans += r-l+1;
            r = v.sec;
        }

        l = min(l, v.fir);
    }

    ans += r-l+1;

    cout << ans << endl;
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

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