제출 #645391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645391		gun_gan	Lasers (NOI19_lasers)	C++17	0 / 100	156 ms	55320 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5e5 + 5;
int l, r, curr[N], sum[N];
vector<int> s[2 * N], pt;
multiset<int> S;
map<int, vector<int>> M;
 
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
 
	cin >> l >> r;
	int ans = 0;
	for(int i = 0; i < r; i++) {
		int x; cin >> x;
		for(int j = 0; j < x; j++) {
			int p; cin >> p;
			sum[i] += p;
			M[sum[i]].push_back(i);
			pt.push_back(sum[i]);
		}
		S.insert(sum[i]);
	}
	sort(pt.begin(), pt.end());
	pt.erase(unique(pt.begin(), pt.end()), pt.end());

	int last = 0;
	for(auto [x, v] : M) {
		if(l - x < *S.rbegin()) ans += x - last;
		for(auto j : v) {
			S.erase(S.find(sum[j] - curr[j]));
			curr[j] = x;
			S.insert(sum[j] - curr[j]);
		}
		last = x;
	}
	if(0 < *S.rbegin()) ans += l - last;
	cout << ans << '\n';
}

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