11 files changed, 446 insertions, 0 deletions
diff --git a/17/day1/arboreal.cpp b/17/day1/arboreal.cpp
new file mode 100644
index 0000000..659216b
--- /dev/null
+++ b/17/day1/arboreal.cpp
@@ -0,0 +1,85 @@
+#include <bits/stdc++.h>
+#include <ext/pb_ds/assoc_container.hpp>
+#include <ext/pb_ds/tree_policy.hpp>
+#define f first
+#define s second
+using namespace std;
+using namespace __gnu_pbds;
+using ii = pair<int, int>;
+template<typename T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
+constexpr int MAXN = 100001;
+
+vector<int> T[MAXN + 1];
+ordered_set<int> S[4 * MAXN + 4];
+
+void build(int l = 0, int r = MAXN, int n = 1) {
+	if (l == r) {
+		for (auto& y : T[l]) S[n].insert(y);
+	}
+	else {
+		int m = (l + r) >> 1;
+		build(l, m, n << 1), build(m + 1, r, n << 1 | 1);
+		for (auto& y : S[n << 1]) S[n].insert(y);
+		for (auto& y : S[n << 1 | 1]) S[n].insert(y);
+	}
+}
+
+int query(int xl, int xr, int yl, int yr, int l = 0, int r = MAXN, int n = 1) {
+	if (l > r || l > xr || r < xl) return 0;
+	if (l >= xl && r <= xr) return S[n].order_of_key(yr + 1) - S[n].order_of_key(yl);
+	else {
+		int m = (l + r) >> 1;
+		return query(xl, xr, yl, yr, l, m, n << 1) + query(xl, xr, yl, yr, m + 1, r, n << 1 | 1);
+	}
+}
+ 
+ii P[100001];
+ 
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+
+	int N; cin >> N;
+	for (int i = 0; i < N; ++i) cin >> P[i].f >> P[i].s;
+ 
+	vector<ii> tmp;
+	for (int i = 0; i < N; ++i) tmp.emplace_back(P[i].f, i);
+	sort(begin(tmp), end(tmp));
+	for (int i = 0; i < N; ++i) {
+		if (i && tmp[i].f == tmp[i - 1].f) P[tmp[i].s].f = P[tmp[i - 1].s].f;
+		else P[tmp[i].s].f = i;
+	}
+	tmp.clear();
+	for (int i = 0; i < N; ++i) tmp.emplace_back(P[i].s, i);
+	sort(begin(tmp), end(tmp));
+	for (int i = 0; i < N; ++i) {
+		if (i && tmp[i].f == tmp[i - 1].f) P[tmp[i].s].s = P[tmp[i - 1].s].s;
+		else P[tmp[i].s].s = i;
+	}
+	
+	for (int i = 0; i < N; ++i) T[P[i].f].push_back(P[i].s);
+	build();
+	
+	vector<ii> X, Y;
+	for (int i = 0; i < N; ++i) X.push_back(P[i]), Y.push_back(P[i]);
+ 
+	auto cmpy = [](const ii & a, const ii & b) { return a.s < b.s || (a.s == b.s && a.f < b.f); };
+	sort(begin(X), end(X));
+	sort(begin(Y), end(Y), cmpy);
+	unique(begin(X), end(X));
+	unique(begin(Y), end(Y), cmpy);
+ 
+	int ans = 0;
+	for (int i = 0; i < N; ++i) {
+		auto it = lower_bound(begin(X), end(X), ii(P[i].f, P[i].s));
+		int yh = (next(it) != end(X) && next(it)->f == P[i].f ? next(it)->s : MAXN + 1);
+		int yl = (it != begin(X) && prev(it)->f == P[i].f ? prev(it)->s : -2);
+ 
+		it = lower_bound(begin(Y), end(Y), ii(P[i].f, P[i].s), cmpy);
+		int xh = (next(it) != end(Y) && next(it)->s == P[i].s ? next(it)->f : MAXN + 1);
+		int xl = (it != begin(Y) && prev(it)->s == P[i].s ? prev(it)->f : -2);
+ 
+		int q = query(xl + 1, xh - 1, yl + 1, yh - 1);
+		if (q > 1) ++ans;
+	}
+	cout << ans << '\n';
+}
diff --git a/17/day1/ingrass.cpp b/17/day1/ingrass.cpp
new file mode 100644
index 0000000..984fe20
--- /dev/null
+++ b/17/day1/ingrass.cpp
@@ -0,0 +1,35 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+
+ii P[50005];
+
+bool ccw(ii a, ii b, ii c) { return (ll)(b.f - a.f) * (c.s - a.s) - (ll)(c.f - a.f) * (b.s - a.s) > 0; }
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+	int N; cin >> N;
+	for (int i = 0; i < N; ++i) cin >> P[i].f >> P[i].s;
+	int m = min_element(P, P + N) - P;
+	vector<pair<double, int>> A;
+	for (int i = 0; i < N; ++i) {
+		if (i != m) A.emplace_back(atan2(P[i].s - P[m].s, P[i].f - P[m].f), i);
+	}
+	sort(begin(A), end(A));
+	vector<int> S;
+	vector<ii> ans;
+	for (int i = 0; i < A.size(); ++i) {
+		ans.emplace_back(m, A[i].s);
+		while (i) {
+			ans.emplace_back(A[i].s, S.back());
+			if (S.size() <= 1 || ccw(P[A[i].s], P[S[S.size() - 2]], P[S.back()])) break;
+			else S.pop_back();
+		}
+		S.push_back(A[i].s);
+	}
+	cout << 3 * N - 2 * S.size() - 4 << ' ' << ans.size() << '\n';
+	for (auto& p : ans) cout << p.f + 1 << ' ' << p.s + 1 << '\n';
+}
+\ No newline at end of file
diff --git a/17/day1/palindrome.cpp b/17/day1/palindrome.cpp
new file mode 100644
index 0000000..dbf5fd6
--- /dev/null
+++ b/17/day1/palindrome.cpp
@@ -0,0 +1,30 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int N, s[100001], dp[100001][606];
+inline int & get(int i, int j) { return dp[i][N - j - i + 301]; }
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
+
+	cin >> N;
+	for (int i = 0; i < N; ++i) cin >> s[i];
+
+	memset(dp, '?', sizeof dp);
+	get(0, N) = 0;
+	for (int i = 0; i < N; ++i) {
+		for (int j = min(N - i + 300, N); j >= max(N - i - 300, i); --j) {
+			get(i + 1, j) = min(get(i, j) + 1, get(i + 1, j));
+			get(i, j - 1) = min(get(i, j) + 1, get(i, j - 1));
+			if (s[i] == s[j - 1]) get(i + 1, j - 1) = min(get(i, j), get(i + 1, j - 1));
+		}
+	}
+
+	int ans = 1e9;
+	for (int i = 0; i < N; ++i) {
+		if (N - 2 * i + 301 >= 0 && N - 2 * i + 301 < 606) ans = min(get(i, i), ans);
+		if (N - 2 * i + 300 >= 0 && N - 2 * i + 300 < 606) ans = min(get(i, i + 1), ans);
+	}
+	if (ans <= 300) cout << ans << '\n';
+	else cout << "many\n";
+}
+\ No newline at end of file
diff --git a/17/day2/cookie.cpp b/17/day2/cookie.cpp
new file mode 100644
index 0000000..d03e72f
--- /dev/null
+++ b/17/day2/cookie.cpp
@@ -0,0 +1,37 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using pl = pair<ll, ll>;
+
+ll C[5005], D[5005];
+pl DP[5005][5005];
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+
+	ll N, T, RA, RB;
+	cin >> N >> T >> RA >> RB;
+	for (int i = 0; i < N; ++i) cin >> C[i];
+	for (int i = 0; i < N; ++i) cin >> D[i];
+	
+	memset(DP, 63, sizeof(DP));
+	DP[0][0] = pl(0, 0);
+	ll ans = T;
+	for (int i = 0; i <= N; ++i) {
+		for (int j = 0; j <= N; ++j) {
+			ll r = 1 + i * RA + j * RB;
+			if (i < N) {
+				ll t = max((C[i] + DP[i][j].s + r - 1) / r, 0ll);
+				DP[i + 1][j] = min(pl(DP[i][j].f + t, -t * r + C[i] + DP[i][j].s), DP[i + 1][j]);
+			}
+			if (j < N) {
+				ll t = max((D[j] + DP[i][j].s + r - 1) / r, 0ll);
+				DP[i][j + 1] = min(pl(DP[i][j].f + t, -t * r + D[j] + DP[i][j].s), DP[i][j + 1]);
+			}
+			ans = min(DP[i][j].f + max((T + DP[i][j].s + r - 1) / r, 0ll), ans);
+		}
+	}
+	cout << ans << '\n';
+}
+\ No newline at end of file
diff --git a/17/day2/lazybubblesort.cpp b/17/day2/lazybubblesort.cpp
new file mode 100644
index 0000000..8395298
--- /dev/null
+++ b/17/day2/lazybubblesort.cpp
@@ -0,0 +1,20 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int A[100001];
+
+int main() {
+	int N, K; cin >> N >> K;
+	for (int i = 0; i < N; ++i) cin >> A[i];
+	multiset<int> S;
+	vector<int> ans;
+	for (int i = 0; i < N; ++i) {
+		if (S.size() < K || A[i] > *begin(S)) {
+			if (S.size() == K) ans.push_back(*begin(S)), S.erase(begin(S));
+			S.insert(A[i]);
+		}
+		else ans.push_back(A[i]);
+	}
+	while (S.size()) ans.push_back(*begin(S)), S.erase(begin(S));
+	for (auto& x : ans) cout << x << '\n';
+}
+\ No newline at end of file
diff --git a/17/day3/balancing.cpp b/17/day3/balancing.cpp
new file mode 100644
index 0000000..c5fa7c6
--- /dev/null
+++ b/17/day3/balancing.cpp
@@ -0,0 +1,23 @@
+#include <bits/stdc++.h>
+using namespace std;
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+	string S; cin >> S;
+	int N = S.size(), cnt = 0;
+	if (count(begin(S), end(S), 'G') << 1 != N) {
+		cout << "NO\n";
+		return 0;
+	}
+	unordered_set<int> M[2];
+	for (int i = 0; i < N; ++i) {
+		if (S[i] != S[(i-1+N)%N]) M[S[i] == 'G'].insert(cnt);
+		cnt += (S[i] == 'G' ? 1 : -1);
+		if (S[i] != S[(i+1)%N] && M[S[i] == 'G'].find(cnt - (S[i] == 'G' ? 1 : -1)) != end(M[S[i] == 'G'])) {
+			cout << "YES\n";
+			return 0;
+		}
+	}
+	cout << "NO\n";
+	return 0;
+}
+\ No newline at end of file
diff --git a/17/day3/timeline.cpp b/17/day3/timeline.cpp
new file mode 100644
index 0000000..a6b8e30
--- /dev/null
+++ b/17/day3/timeline.cpp
@@ -0,0 +1,41 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ii = pair<int, int>;
+
+int dist[5005];
+vector<ii> G[5005];
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
+	int N, M, C; cin >> N >> M >> C;
+	for (int u = 1; u <= N; ++u) {
+		int s, t; cin >> s >> t;
+		G[u].emplace_back(-s, 0);
+		G[0].emplace_back(t, u);
+	}
+	while (C--) {
+		int a, b, x; cin >> a >> b >> x;
+		G[a].emplace_back(-x, b);
+	}
+	memset(dist, '?', sizeof dist);
+	dist[0] = 0;
+	for (int i = 0; i < N; ++i) {
+		for (int u = 0; u <= N; ++u) {
+			for (auto& v : G[u]) {
+				if (dist[u] + v.f < dist[v.s]) dist[v.s] = dist[u] + v.f;
+			}
+		}
+	}
+	for (int u = 0; u <= N; ++u) {
+		for (auto& v : G[u]) {
+			if (dist[u] < 0 || dist[u] > M || dist[u] + v.f < dist[v.s]) {
+				cout << "impossible\n";
+				return 0;
+			}
+		}
+	}
+	for (int u = 1; u <= N; ++u) cout << dist[u] << '\n';
+	return 0;
+}
+\ No newline at end of file
diff --git a/17/day4/knights.cpp b/17/day4/knights.cpp
new file mode 100644
index 0000000..784abfc
--- /dev/null
+++ b/17/day4/knights.cpp
@@ -0,0 +1,91 @@
+#include <bits/stdc++.h>
+using namespace std;
+using ll = long long;
+constexpr ll INF = 1e12;
+ 
+int dx[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
+int dy[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
+char A[101][101];
+ 
+template<int V, class T = ll> class max_flow {
+	struct edge {
+		int t, rev;
+		T cap, f;
+	};
+	vector<edge> adj[V];
+	int dist[V];
+	int ptr[V];
+	bool bfs(int s, int t) {
+		memset(dist, -1, sizeof dist);
+		dist[s] = 0;
+		queue<int> q({ s });
+		while (!q.empty() && dist[t] == -1) {
+			int n = q.front();
+			q.pop();
+			for (auto& e : adj[n]) {
+				if (dist[e.t] == -1 && e.cap != e.f) {
+					dist[e.t] = dist[n] + 1;
+					q.push(e.t);
+				}
+			}
+		}
+		return dist[t] != -1;
+	}
+	T augment(int n, T amt, int t) {
+		if (n == t) return amt;
+		for (; ptr[n] < adj[n].size(); ptr[n]++) {
+			edge& e = adj[n][ptr[n]];
+			if (dist[e.t] == dist[n] + 1 && e.cap != e.f) {
+				T flow = augment(e.t, min(amt, e.cap - e.f), t);
+				if (flow != 0) {
+					e.f += flow;
+					adj[e.t][e.rev].f -= flow;
+					return flow;
+				}
+			}
+		}
+		return 0;
+	}
+public:
+	void add(int u, int v, T cap = 1, T rcap=0) {
+		adj[u].push_back({ v, (int) adj[v].size(), cap, 0 });
+		adj[v].push_back({ u, (int) adj[u].size() - 1, rcap, 0 });
+	}
+	T calc(int s, int t) {
+		T flow = 0;
+		while (bfs(s, t)) {
+			memset(ptr, 0, sizeof ptr);
+			while (T df = augment(s, INF, t)) flow += df;
+		}
+		return flow;
+	}
+	void clear() {
+		for (int n = 0; n < V; n++) adj[n].clear();
+	}
+};
+ 
+int main() {
+	int R, C; 
+	cin >> R >> C;
+	int ans = R * C;
+	for (int i = 0; i < R; ++i) {
+		for (int j = 0; j < C; ++j) cin >> A[i][j];
+	}
+ 
+	max_flow<101*101> MF;
+	for (int i = 0; i < R; ++i) {
+		for (int j = 0; j < C; ++j) {
+			if (A[i][j] == '#') { --ans; continue; }
+			if (i + j & 1) {
+				MF.add(10000, i * C + j, (A[i][j] == 'C' ? INF : 1));
+				for (int d = 0; d < 8; ++d) {
+					int x = i + dx[d], y = j + dy[d];
+					if (x < 0 || x >= R || y < 0 || y >= C || A[x][y] == '#') continue;
+					MF.add(i * C + j, x * C + y, INF);
+				}
+			}
+			else MF.add(i * C + j, 10001, (A[i][j] == 'C' ? INF : 1));
+		}
+	}
+	cout << ans - MF.calc(10000, 10001) << '\n';
+}
+\ No newline at end of file
diff --git a/17/day4/stock_trading.cpp b/17/day4/stock_trading.cpp
new file mode 100644
index 0000000..c2aa679
--- /dev/null
+++ b/17/day4/stock_trading.cpp
@@ -0,0 +1,21 @@
+#include <bits/stdc++.h>
+using namespace std;
+using ll = long long;
+
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0);
+
+	int N, L;
+	cin >> N >> L;
+
+	multiset<ll> S;
+	ll ans = 0;
+	for (int i = 0, b, s; i < N; ++i) {
+		cin >> b >> s;
+		ans = max(ans - (i >= L ? *begin(S) : 0) + s, ans);
+		S.insert({ b, s });
+		if (i >= L) S.erase(begin(S)), S.erase(prev(end(S)));
+	}
+	for (auto it = S.begin(); L; ++it, --L) ans -= *it;
+	cout << ans << endl;
+}
+\ No newline at end of file
diff --git a/17/day4/tuning.cpp b/17/day4/tuning.cpp
new file mode 100644
index 0000000..d2bddd9
--- /dev/null
+++ b/17/day4/tuning.cpp
@@ -0,0 +1,22 @@
+#include <bits/stdc++.h>
+using namespace std;
+ 
+int main() {
+	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
+ 
+	int N;
+	cin >> N;
+	int ans = 1, cnt = 1;
+	for (int i = 2; i < N; ++i) {
+		if (cnt) {
+			cout << ans << ' ' << i << endl;
+			string s; cin >> s;
+			s[0] == 'S' ? ++cnt : --cnt;
+		}
+		else {
+			ans = i;
+			++cnt;
+		}
+	}
+	cout << (cnt ? ans : N) << endl;
+}
+\ No newline at end of file
diff --git a/17/day5/trip.cpp b/17/day5/trip.cpp
new file mode 100644
index 0000000..35ded67
--- /dev/null
+++ b/17/day5/trip.cpp
@@ -0,0 +1,41 @@
+#include <bits/stdc++.h>
+#define f first
+#define s second
+using namespace std;
+using ll = long long;
+using ii = pair<int, int>;
+
+vector<ii> G[100001];
+unordered_map<int, ll> A[100001], B[100001];
+ 
+ll dfs(int u, int p) {
+	sort(begin(G[u]), end(G[u]));
+	ll ret = 0, sa = 1, tmp = 0, l = -1;
+	++A[u][0], ++B[u][1e9+7];
+	for (auto& v : G[u]) {
+		if (v.s != p) {
+			ret += dfs(v.s, u);
+			ll ca = 0, cb = 0;
+			for (auto& x : A[v.s]) {
+				if (x.f < v.f) ca += x.s, A[u][v.f] += x.s;
+			}
+			for (auto& x : B[v.s]) {
+				if (x.f > v.f) cb += x.s, B[u][v.f] += x.s;
+			}
+			ret += cb * sa, sa += ca;
+			if (v.f != l) l = v.f, tmp = ca;
+			else ret -= cb * tmp, tmp += ca;
+		}
+	}
+	return ret + sa - 1;
+}
+ 
+int main() {
+	int N;
+	cin >> N;
+	for (int i = 1, a, b, e; i < N; ++i) {
+		cin >> a >> b >> e;
+		G[a].emplace_back(e, b), G[b].emplace_back(e, a);
+	}
+	cout << dfs(1, 0) << '\n';
+}
+\ No newline at end of file