제출 #1314673

#제출 시각아이디문제언어결과실행 시간메모리
1314673joshjuiceLasers (NOI19_lasers)C++20
100 / 100
89 ms8588 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef deque<int> dqi;
typedef pair<ll, ll> pll;

#define ppf pop_front
#define pf push_front
#define pb push_back
#define fr first
#define sc second
#define all(a) a.begin(), a.end()
#define sr(a) sort(all(a))
#define sz(a) a.size()
#define rep(x, a, b) for(auto x=a;(a<b?x<b:x>b);(a<b?x++:x--))
#define mnto(x,y) x = min(x, (__typeof__(x))y)
#define mxto(x,y) x = max(x, (__typeof__(x))y)

const ll INF1 = 1e18;
const ll INF2 = 1e15;
const ll INF3 = 1e14;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  ll l;
  int r, x;
  cin >> l >> r;
  vector<pll> avail;
  rep(i, 0, r) {
    cin >> x;
    vll a(x);
    rep(i, 0, x) cin >> a[i];
    vll ps(x+1, 0);
    rep(i, 0, x) ps[i+1] = ps[i]+a[i];
    ll total = ps[x];
    ll d = l-total; //remaining guranteed spaces
    rep(j, 0, x) {
      ll leftl = ps[j]+1;
      ll leftr = ps[j]+a[j];
      ll rightl = leftl+d;
      ll rightr = leftr+d;
      ll gl = max(leftl, rightl);
      ll gr = min(leftr, rightr);
      if (gl <= gr) {
        avail.emplace_back(gl, gr); 
      }
    }
  }
  sr(avail);
  vector<pll> merged;
  for (auto [l, r] : avail) {
    if (!sz(merged) || l > merged.back().sc+1) merged.emplace_back(l, r);
    else mxto(merged.back().sc, r);
  }
  ll ans = 0;
  for (auto [l, r] : merged) ans += r-l+1;
  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...