제출 #1292579

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1292579		yonatanl	Lasers (NOI19_lasers)	C++20	100 / 100	376 ms	66720 KiB

lasers

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>

#define rep(i, s, e) for (ll i = s; i < e; i++)
#define upmax(a, b) a = max(a, b)
#define upmin(a, b) a = min(a, b)

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;

const ll INF = 1e18;

void solve() {
	ll l, n;
	cin >> l >> n;
	vvll arr(n);
	vll x(n);
	vll sum(n);
	rep(i, 0, n) {
		cin >> x[i];
		arr[i].resize(x[i]);
		rep(j, 0, x[i]) {
			cin >> arr[i][j];
			sum[i] += arr[i][j];
		}
	}
	set<pair<ll, pll>> sR; // {right, {idx, i}}
	ll left = 0; // Max left of all rows
	rep(i, 0, n) {
		sR.insert({ sum[i], {0, i}});
	}
	auto temp = --(sR.end());
	ll right = (*temp).first;
	ll lastLeft = l - right; // [1, a] is good already
	ll ans = lastLeft;
	left = lastLeft;
	while (!sR.empty()) {
		/*for (auto& it : sR) {
			cout << it.first << ' ' << it.second.first << " " << it.second.second << endl;
		}
		cout << endl;*/
		auto it = --(sR.end());
		ll right = (*it).first;
		ll idx = (*it).second.first;
		ll i = (*it).second.second;
		upmax(left, sum[i] - right + arr[i][idx]);
		sR.erase(it);
		if (idx < x[i] - 1) sR.insert({ right - arr[i][idx], {idx + 1, i} });
		if (sR.empty()) {
			// [left, l] is good
			ans += l - left;
		}
		else {
			auto it2 = --(sR.end());
			ll curRight = l - (*it2).first;
			if (left < curRight) {
				ans += curRight - left;
				upmax(left, curRight);
			}
		}
	}
	cout << l - ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	solve();
}

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