Submission #1340805

#TimeUsernameProblemLanguageResultExecution timeMemory
1340805NipphitchLasers (NOI19_lasers)C++20
0 / 100
23 ms7624 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int M=1e6+5;

int m,n,p_now,ans;
bool b[M];
vector <pair <int,int>> vec;

bool cmp(pair <int,int> x,pair <int,int> y){
    if(x.first!=y.first) return x.first<y.first;
    else return x.second>y.second;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n;
    for(int i=1;i<=n;i++){
        int c,sum=0;
        cin >> c;
        vector <int> v;
        for(int j=1;j<=c;j++){
            int x;
            cin >> x;
            v.push_back(x);
            sum+=x;
        }
        int mov=(m-sum),qs=0;
        for(int j=0;j<c;j++){
            if(mov>=v[j]) continue;
            int r=qs+v[j],l=qs+mov+1;
            vec.push_back({l,r});
            qs+=v[j];
        }
    }
    /*
    sort(vec.begin(),vec.end(),cmp);
    for(auto [x,y]:vec){
        //cout << x << " " << y << "\n";
        ans+=max(0LL,min(y-p_now,y-x+1));
        p_now=max(p_now,y);
    }
    */
    for(auto [x,y]:vec) for(int i=x;i<=y;i++) b[i]=true;
    for(int i=1;i<=m;i++) if(b[i]) ans++;
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...