Submission #815942

#	Time	Username	Problem	Language	Result	Execution time	Memory
815942		devariaota	Lasers (NOI19_lasers)	C++17	100 / 100	120 ms	9868 KiB

lasers

#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int MOD=1e9+7;
signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int len, n, ans=0; cin >> len >> n;
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  while(n--) {
    int x, sum=len, pre=1; cin >> x;
    vector<int> a(x);
    for(int &p : a) cin >> p, sum-=p;
    for(int p : a) {
      if(p>sum) pq.push({pre+sum, pre+p-1});
      pre+=p;
    }
  }
  while(!pq.empty()) {
    int l=pq.top().first, r=pq.top().second;
    pq.pop();
    while(!pq.empty() && pq.top().first<=r) r=max(r, pq.top().second), pq.pop();
    ans+=r-l+1;
  }
  cout << ans << '\n';
    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