제출 #1345547

#제출 시각아이디문제언어결과실행 시간메모리
1345547lyra_g13Lasers (NOI19_lasers)C++20
100 / 100
61 ms8768 KiB
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  ll n, rows;
  cin >> n >> rows;

  vector<pair<ll, ll>> a;

  for (int i = 0; i < rows; i++) {
    ll x;
    cin >> x;

    ll tot = 0;

    vector<ll> block(x);
    for (int j = 0; j < x; j++) {
      cin >> block[j];

      tot += block[j];
    }

    ll freespace = n - tot;

    ll pref = 0;
    for (int k = 0; k < x; k++) {
      ll l = pref + freespace;
      ll r = pref + block[k] - 1;

      if (l <= r) {
        a.push_back({l, r});
      }
      pref += block[k];
    }
  }

  if (a.size() == 0) {
    cout << 0 << "\n";
    return 0;
  }
  sort(a.begin(), a.end());
  ll ans = 0;
  ll left = a[0].first;
  ll right = a[0].second;
  for (int i = 1; i < a.size(); i++) {
    ll l = a[i].first;
    ll r = a[i].second;

    if (l > right + 1) {
      ans += right - left + 1;
      left = l;
      right = r;
    } else
      right = max(right, r);
  }

  ans += right - left + 1;
  cout << ans << "\n";
}
#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...