ICPC Seoul Regional 2022 본선 풀이

D번: 중요한

#include <bits/stdc++.h>
#define INF 0x7fffffff
#define SIZE 100001
using namespace std;
int seg[SIZE << 1][2];
void update(int id, int idx, int val) {
    seg[SIZE + idx][id] = val;
    for (int i = (SIZE + idx) >> 1; i > 0; i >>= 1) seg[i][id] = min(seg[i << 1][id], seg[i << 1 | 1][id]);
}
int query(int id, int left, int right) {
    int ret = INF;
    for (int l = left + SIZE, r = right + SIZE; l <= r; l >>= 1, r >>= 1) {
        if (l & 1) ret = min(ret, seg[l++][id]);
        if (~r & 1) ret = min(ret, seg[r--][id]);
    }
    return ret;
}
int pos(int val, int right) {
	right += SIZE;
    while (seg[right][0] > val) right = (right - 1) >> 1;
    while (right < SIZE) {
        if (seg[right << 1 | 1][0] <= val) right = right << 1 | 1;
        else right <<= 1;
    }
    return right - SIZE;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; vector<int> a(n + 1), psum(n + 1); vector<vector<int>> dp(n + 1, vector<int>(2));
	for (int i = 1; i <= n; i++) {
		cin >> a[i]; psum[i] = psum[i - 1] + a[i];
	}
	dp[1][0] = dp[1][1] = a[1]; update(0, 1, a[1]); update(1, 1, a[1]);
	for (int i = 2; i <= n; i++) {
		int idx = pos(psum[i], i - 1);
		dp[i][0] = min(query(1, idx + 1, i - 1), psum[i] - psum[idx - 1]);
		dp[i][1] = max(a[i], psum[i - 1] - psum[pos(psum[i - 1], i - 1) - 1]);
		update(0, i, dp[i][1] + psum[i - 1]);
		update(1, i, dp[i][1]);
	}
	cout << min(dp[n][0], dp[n][1]) << "\n";
	return 0;
}

 

E번: 것은

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int, int> pi;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int m, n, k; cin >> m >> n >> k;
	int v, w; cin >> v >> w; vector<pi> tmp[n], adj[m];
	vector<pair<pi, int>> vert(m); vector<int> goal(m, -1);
	map<pair<pi, int>, bool> forb; map<pi, int> mp;
	for (int i = 0; i < m; i++) {
		int x, y, c; cin >> x >> y >> c;
		mp[{x, y}] = i;
		if (w == y) goal[i] = c;
		tmp[x].push_back({y, c});
		vert[i] = {{x, y}, c};
	}
	for (int i = 0; i < k; i++) {
		int x, y, z; cin >> x >> y >> z;
		forb[{{x, y}, z}] = true;
	}
	for (int i = 0; i < m; i++) {
		int x = vert[i].first.first, y = vert[i].first.second;
		for (auto u: tmp[y]) {
			if (forb.find({{x, y}, u.first}) == forb.end()) {
				adj[i].push_back({mp[{y, u.first}], vert[i].second + u.second});
			}
		}
	}
	if (v == w) {cout << "0\n"; return 0;}
	int ans = INF;
	for (auto u: tmp[v]) {
		int start = mp[{v, u.first}];
		vector<int> d(m, INF); d[start] = 0;
		priority_queue<pi> pq;
		pq.push({0, start});
		while (!pq.empty()) {
			int cost = -pq.top().first, cur = pq.top().second; pq.pop();
			for (int i = 0; i < adj[cur].size(); i++) {
				int nxt = adj[cur][i].first, cst = adj[cur][i].second;
				if (d[nxt] > cost + cst) {
					d[nxt] = cost + cst;
					pq.push({-d[nxt], nxt});
				}
			}
		}
		for (int i = 0; i < m; i++) {
			if (goal[i] >= 0) ans = min(ans, u.second + d[i] + goal[i]);
		}
	}
	if (ans == INF) cout << "-1\n";
	else cout << ans / 2 << "\n";
	return 0;
}

 

F번: 꺾이지

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, k, rightmax; cin >> n >> k; vector<ll> dp(n);
	cin >> rightmax >> rightmax;
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		if (rightmax < a) dp[i] = dp[i - 1] + a - rightmax;
		else dp[i] = dp[i - 1];
		rightmax = max(rightmax, b);
	}
	int last = 0; ll ans = 0;
	while (k--) {
		int tmp; cin >> tmp; tmp--;
		ans += abs(dp[tmp] - dp[last]);
		last = tmp;
	}
	cout << ans << "\n";
	return 0;
}

 

I번: 않는

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, k, rightmax; cin >> n >> k; vector<ll> dp(n);
	cin >> rightmax >> rightmax;
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		if (rightmax < a) dp[i] = dp[i - 1] + a - rightmax;
		else dp[i] = dp[i - 1];
		rightmax = max(rightmax, b);
	}
	int last = 0; ll ans = 0;
	while (k--) {
		int tmp; cin >> tmp; tmp--;
		ans += abs(dp[tmp] - dp[last]);
		last = tmp;
	}
	cout << ans << "\n";
	return 0;
}

 

J번: 마음

#include <bits/stdc++.h>
using namespace std;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	string s; cin >> s; int n = s.size();
	int level = 0; long long ans = 0;
	for (int i = 0; i < n; i++) {
		level += (s[i] == '(') * 2 - 1;
		if (s[i] == ')' && s[i - 1] == '(') ans += level;
	}
	cout << ans << "\n";
	return 0;
}