제출 #1311987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1311987		samarthkulkarni	Lasers (NOI19_lasers)	C++20	100 / 100	101 ms	35588 KiB

lasers

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}





void solution() {
	ll L, R; cin >> L >> R;

	vector<vi> walls(R);

	for (int i = 0; i < R; i++) {
		ll x; cin >> x;
		walls[i].resize(x);
		for (ll &z : walls[i]) cin >> z;
	}	


	
	vector<pr> cant;

	for (int i = 0; i < R; i++) {
		ll sum = accumulate(all(walls[i]), 0ll);

		ll dif = L-sum+1;
		for (int j = walls[i].size()-1; j >= 0; j--) {


			ll r = sum;

			sum -= walls[i][j];
			ll l = sum + dif;


			if (l <= r) cant.push_back({l, r});

		}

	}

	if (cant.size() == 0) {
		cout << 0 << endl;
		return;
	}

	sort(all(cant));

	vector<pr> nw;
	ll l = cant[0].ff, r = cant[0].ss;
	for (auto [x, y] : cant) {
		if (x <= r) r = max(r, y);
		else {
			nw.push_back({l, r});
			l = x; r = y;
		}
	}
	nw.push_back({l, r});


	ll ans = 0;
	for (auto [x, y] : nw) {
		ans += y-x+1;
	}
	cout << ans << endl;


}

• Subtask 1: 10 / 10
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 22 / 22
• Subtask 6: 13 / 13