제출 #699103

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
699103		mickeydesai	Lasers (NOI19_lasers)	C++14	100 / 100	434 ms	101360 KiB

lasers

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define ii pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define ll long long
#define FORU(i,j,n) for(int i=(j);i<=(n);i++)
#define FORD(i,j,n) for(int i=(j);i>=(n);i--)
using namespace std;

const int N=5e5+5;
int L,n;
int k[N];
vi x[N];
vi l[N],r[N];
set<ii> ans;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>L>>n;
    FORU(i,1,n)
    {
        cin>>k[i];
        x[i].resize(k[i]+2,0);
        l[i].resize(k[i]+2,0);
        r[i].resize(k[i]+2,0);
        FORU(j,1,k[i])cin>>x[i][j],l[i][j]=l[i][j-1]+x[i][j];
        FORD(j,k[i],1)r[i][j]=r[i][j+1]+x[i][j];

        FORU(j,1,k[i])
            if(l[i][j-1]+r[i][j]+x[i][j]>L)ans.insert({L-r[i][j]+1,l[i][j]});
    }
    int res=0,pre=1,cur=0;
    for(auto x:ans)
    {
        if(cur<x.fi)
        {
            res+=cur-pre+1;
            pre=x.fi;cur=x.se;
        }
        else cur=max(cur,x.se);
    }
    res+=cur-pre+1;
    cout<<res;
    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