Submission #645392

#	Time	Username	Problem	Language	Result	Execution time	Memory
645392		gun_gan	Lasers (NOI19_lasers)	C++17	100 / 100	961 ms	87924 KiB

lasers

#include <bits/stdc++.h>
using namespace std;
 
const int N = 5e5 + 5;
int l, r, curr[N], sum[N];
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);
		}
		S.insert(sum[i]);
	}

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

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