Submission #1366366

#TimeUsernameProblemLanguageResultExecution timeMemory
1366366hyyhLasers (NOI19_lasers)C++20
100 / 100
166 ms8052 KiB
#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <iomanip>
#include <set>
#include <bitset>
#include <unordered_map>

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using piii = tuple<int,int,int>;
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x),end(x)
#define m_p make_pair

int main(){
    int n;cin >> n;
    int m;cin >> m;
    // auto add = [&](int l,int r){
    //     int lmd = n-r;
    //     int rmd = l+r;
    //     if(lmd <= rmd) vc.emplace_back(lmd,rmd);
    // };
    vector<pii> blocked;
    for(int i{};i < m;i++){
        vector<pii> vc;
        int k;cin >> k;
        vector<int> pref = {0};
        for(int j{};j < k;j++){
            int g;cin >> g;
            pref.emplace_back(pref.back()+g);
        }
        for(int j{};j <= k;j++){
            vc.emplace_back(pref[j]+1,n-(pref[k]-pref[j]));
        }
        int maxi = 0;
        for(auto [a,b]:vc){
            if(maxi+1 <= a-1){
                blocked.emplace_back(maxi+1,a-1);
            }
            maxi = max(b,maxi);
        }
    }
    // sort(all(vc));
    int ans = 0;
    sort(all(blocked));
    int end = 0;
    for(auto [a,b]:blocked){
        end = max(end,a-1);
        //cout << a << " " << b << endl;
        if(b > end){
            ans += b-end;
            end = b;
        }
    }
    cout << ans;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...