codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1324.md (4296B)


      1 Source: https://codeforces.com/blog/entry/74714
      2 
      3 Suddendly, all ideas of this contest are mine. And I'm very sorry about one missing small test in the problem B. This is the biggest mistake I made during the preparation of this round.
      4 
      5 [1324A - Yet Another Tetris Problem](/contest/1324/problem/A "Codeforces Round 627 (Div. 3)")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 for i in range(int(input())):
     15 	n = int(input())
     16 	cnto = sum(list(map(lambda x: int(x) % 2, input().split())))
     17 	print('YES' if cnto == 0 or cnto == n else 'NO')
     18 ```
     19 
     20 [1324B - Yet Another Palindrome Problem](/contest/1324/problem/B "Codeforces Round 627 (Div. 3)")
     21 
     22 **Tutorial**
     23 
     24 Tutorial is loading...
     25 
     26 **Solution**
     27 
     28 ```
     29 for i in range(int(input())):
     30 	n = int(input())
     31 	s = list(map(int, input().split()))
     32 	ok = False
     33 	for i in range(n):
     34 		for j in range(i + 2, n):
     35 			if s[i] == s[j]: ok = True
     36 	print('YES' if ok else 'NO')
     37 ```
     38 
     39 [1324C - Frog Jumps](/contest/1324/problem/C "Codeforces Round 627 (Div. 3)")
     40 
     41 **Tutorial**
     42 
     43 Tutorial is loading...
     44 
     45 **Solution**
     46 
     47 ```
     48 #include <bits/stdc++.h>
     49 
     50 using namespace std;
     51 
     52 int main() {
     53 #ifdef _DEBUG
     54 	freopen("input.txt", "r", stdin);
     55 //	freopen("output.txt", "w", stdout);
     56 #endif
     57 	
     58 	int t;
     59 	cin >> t;
     60 	while (t--) {
     61 		string s;
     62 		cin >> s;
     63 		vector<int> pos;
     64 		pos.push_back(0);
     65 		for (int i = 0; i < int(s.size()); ++i) {
     66 			if (s[i] == 'R') pos.push_back(i + 1);
     67 		}
     68 		pos.push_back(s.size() + 1);
     69 		int ans = 0;
     70 		for (int i = 0; i < int(pos.size()) - 1; ++i) {
     71 			ans = max(ans, pos[i + 1] - pos[i]);
     72 		}
     73 		cout << ans << endl;
     74 	}
     75 	
     76 	return 0;
     77 }
     78 ```
     79 
     80 [1324D - Pair of Topics](/contest/1324/problem/D "Codeforces Round 627 (Div. 3)")
     81 
     82 **Tutorial**
     83 
     84 Tutorial is loading...
     85 
     86 **Solution**
     87 
     88 ```
     89 #include <bits/stdc++.h>
     90 
     91 using namespace std;
     92 
     93 int main() {
     94 #ifdef _DEBUG
     95 	freopen("input.txt", "r", stdin);
     96 //	freopen("output.txt", "w", stdout);
     97 #endif
     98 	
     99 	int n;
    100 	cin >> n;
    101 	vector<int> a(n), b(n);
    102 	for (auto &it : a) cin >> it;
    103 	for (auto &it : b) cin >> it;
    104 	vector<int> c(n);
    105 	for (int i = 0; i < n; ++i) {
    106 		c[i] = a[i] - b[i];
    107 	}
    108 	sort(c.begin(), c.end());
    109 	
    110 	long long ans = 0;
    111 	for (int i = 0; i < n; ++i) {
    112 		if (c[i] <= 0) continue;
    113 		int pos = lower_bound(c.begin(), c.end(), -c[i] + 1) - c.begin();
    114 		ans += i - pos;
    115 	}
    116 	
    117 	cout << ans << endl;
    118 	
    119 	return 0;
    120 }
    121 ```
    122 
    123 [1324E - Sleeping Schedule](/contest/1324/problem/E "Codeforces Round 627 (Div. 3)")
    124 
    125 **Tutorial**
    126 
    127 Tutorial is loading...
    128 
    129 **Solution**
    130 
    131 ```
    132 #include <bits/stdc++.h>
    133 
    134 using namespace std;
    135 
    136 bool in(int x, int l, int r) {
    137 	return l <= x && x <= r;
    138 }
    139 
    140 int main() {
    141 #ifdef _DEBUG
    142 	freopen("input.txt", "r", stdin);
    143 //	freopen("output.txt", "w", stdout);
    144 #endif
    145 	
    146 	int n, h, l, r;
    147 	cin >> n >> h >> l >> r;
    148 	vector<int> a(n);
    149 	for (auto &it : a) cin >> it;
    150 	vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MIN));
    151 	dp[0][0] = 0;
    152 	int sum = 0;
    153 	for (int i = 0; i < n; ++i) {
    154 		sum += a[i];
    155 		for (int j = 0; j <= n; ++j) {
    156 			dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + in((sum - j) % h, l, r));
    157 			if (j < n) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + in((sum - j - 1) % h, l, r));
    158 		}
    159 	}
    160 	
    161 	cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
    162 	
    163 	return 0;
    164 }
    165 ```
    166 
    167 [1324F - Maximum White Subtree](/contest/1324/problem/F "Codeforces Round 627 (Div. 3)")
    168 
    169 **Tutorial**
    170 
    171 Tutorial is loading...
    172 
    173 **Solution**
    174 
    175 ```
    176 #include <bits/stdc++.h>
    177 
    178 using namespace std;
    179 
    180 vector<int> a;
    181 vector<int> dp;
    182 vector<int> ans;
    183 vector<vector<int>> g;
    184 
    185 void dfs(int v, int p = -1) {
    186 	dp[v] = a[v];
    187 	for (auto to : g[v]) {
    188 		if (to == p) continue;
    189 		dfs(to, v);
    190 		dp[v] += max(dp[to], 0);
    191 	}
    192 }
    193 
    194 void dfs2(int v, int p = -1) {
    195 	ans[v] = dp[v];
    196 	for (auto to : g[v]) {
    197 		if (to == p) continue;
    198 		dp[v] -= max(0, dp[to]);
    199 		dp[to] += max(0, dp[v]);
    200 		dfs2(to, v);
    201 		dp[to] -= max(0, dp[v]);
    202 		dp[v] += max(0, dp[to]);
    203 	}
    204 }
    205 
    206 int main() {
    207 #ifdef _DEBUG
    208 	freopen("input.txt", "r", stdin);
    209 //	freopen("output.txt", "w", stdout);
    210 #endif
    211 	
    212 	int n;
    213 	cin >> n;
    214 	a = dp = ans = vector<int>(n);
    215 	g = vector<vector<int>>(n);
    216 	for (int i = 0; i < n; ++i) {
    217 		cin >> a[i];
    218 		if (a[i] == 0) a[i] = -1;
    219 	}
    220 	for (int i = 0; i < n - 1; ++i) {
    221 		int x, y;
    222 		cin >> x >> y;
    223 		--x, --y;
    224 		g[x].push_back(y);
    225 		g[y].push_back(x);
    226 	}
    227 	
    228 	dfs(0);
    229 	dfs2(0);
    230 	for (auto it : ans) cout << it << " ";
    231 	cout << endl;
    232 	
    233 	return 0;
    234 }
    235 ```