Submission #1249104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249104		nasjes	Lasers (NOI19_lasers)	C++20	100 / 100	114 ms	85656 KiB

lasers

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 2*(1e6)+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m, k;
vll a[dim];
ll pr[dim];
ll sf[dim];
ll sz[dim];
int main() {

    ll  u, w,q,sm,   v, y;
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >>sm>> n;
    vector<pll> subs;
    for(int i=1; i<=n; i++){
        cin>>m;
        a[i].resize(m+5);
        for(int j=0; j<=m+5; j++){
            sf[j]=0;
            pr[j]=0;
        }
        ll l, r;
        for(int j=1; j<=m; j++){
            cin>>u;
            a[i][j]=u;
            pr[j]=pr[j-1]+a[i][j];
        }
        for(int j=m; j>=1; j--){
            sf[j]=sf[j+1]+a[i][j];
        }
        for(int j=1; j<=m; j++){
            l=pr[j];
            r=sm-sf[j]+1;
            if(l>=r)subs.pb({r, l});
        }
    }
    ll ans=0;
    sort(subs.begin(), subs.end());
    ll end=0;
    for(auto el:subs){
        //cout<<el.fi<<" "<<el.se<<endl;
        if(el.se<=end)continue;
        ll st=max(el.fi, end+1);

        if(st>el.se)continue;
        ans+=(el.se-st+1);
        end=el.se;
    }
    cout<<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