codeforces-scrape

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

1304.md (9884B)


      1 Source: https://codeforces.com/blog/entry/73934
      2 
      3 [1304A — Two Rabbits](https://codeforces.com/contest/1304/problem/A)
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution**
     10 
     11 ```
     12 #include <bits/stdc++.h>
     13 using namespace std;
     14 
     15 int main()
     16 {
     17 	int tc;
     18 	cin >> tc;
     19 	while (tc--)
     20 	{
     21 		int x, y, a, b;
     22 		cin >> x >> y >> a >> b;
     23 		cout << ((y - x) % (a + b) == 0 ? (y - x) / (a + b) : -1) << endl;
     24 	}
     25 }
     26 ```
     27 
     28 [1304B — Longest Palindrome](https://codeforces.com/contest/1304/problem/B)
     29 
     30 **Tutorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Solution**
     35 
     36 ```
     37 #include <bits/stdc++.h>
     38 using namespace std;
     39 
     40 const int MAX_N = 100;
     41 string s[MAX_N];
     42 
     43 int main()
     44 {
     45 	set<string> dict;
     46 	int n, m, i;
     47 	cin >> n >> m;
     48 	for (i = 0; i < n; i++)
     49 	{
     50 		cin >> s[i];
     51 		dict.insert(s[i]);
     52 	}
     53 	vector<string> left, right;
     54 	string mid;
     55 	for (i = 0; i < n; i++)
     56 	{
     57 		string t = s[i];
     58 		reverse(t.begin(), t.end());
     59 		if (t == s[i])
     60 			mid = t;
     61 		else if (dict.find(t) != dict.end())
     62 		{
     63 			left.push_back(s[i]);
     64 			right.push_back(t);
     65 			dict.erase(s[i]);
     66 			dict.erase(t);
     67 		}
     68 	}
     69 	cout << left.size() * m * 2 + mid.size() << endl;
     70 	for (string x : left)
     71 		cout << x;
     72 	cout << mid;
     73 	reverse(right.begin(), right.end());
     74 	for (string x : right)
     75 		cout << x;
     76 	cout << endl;
     77 }
     78 ```
     79 
     80 [1304C — Air Conditioner](https://codeforces.com/contest/1304/problem/C)
     81 
     82 **Tutorial**
     83 
     84 Tutorial is loading...
     85 
     86 **Solution**
     87 
     88 ```
     89 #include <bits/stdc++.h>
     90 using namespace std;
     91 
     92 const int MAX_N = 100;
     93 
     94 int t[MAX_N], lo[MAX_N], hi[MAX_N];
     95 
     96 int main()
     97 {
     98 	int tc;
     99 	cin >> tc;
    100 	while (tc--)
    101 	{
    102 		int n, m, i;
    103 		cin >> n >> m;
    104 		for (i = 0; i < n; i++)
    105 			cin >> t[i] >> lo[i] >> hi[i];
    106 		int prev = 0;
    107 		int mn = m, mx = m;
    108 		bool flag = true;
    109 		for (i = 0; i < n; i++)
    110 		{
    111 			mx += t[i] - prev;
    112 			mn -= t[i] - prev;
    113 			if (mx < lo[i] || mn > hi[i])
    114 			{
    115 				flag = false;
    116 				break;
    117 			}
    118 			mx = min(mx, hi[i]);
    119 			mn = max(mn, lo[i]);
    120 			prev = t[i];
    121 		}
    122 		if (flag)
    123 			cout << "YES\n";
    124 		else
    125 			cout << "NO\n";
    126 	}
    127 }
    128 ```
    129 
    130 [1304D — Shortest and Longest LIS](https://codeforces.com/contest/1304/problem/D)
    131 
    132 **Tutorial**
    133 
    134 Tutorial is loading...
    135 
    136 **Solution**
    137 
    138 ```
    139 #include <bits/stdc++.h>
    140 using namespace std;
    141 
    142 const int MAX_N = 200000;
    143 int ans[MAX_N + 5];
    144 
    145 int main()
    146 {
    147 	int tc;
    148 	cin >> tc;
    149 	while (tc--)
    150 	{
    151 		int n, i, j;
    152 		string s;
    153 		cin >> n >> s;
    154 
    155 		int num = n, last = 0;
    156 		for (i = 0; i < n; i++)
    157 		{
    158 			if (i == n - 1 || s[i] == '>')
    159 			{
    160 				for (j = i; j >= last; j--)
    161 					ans[j] = num--;
    162 				last = i + 1;
    163 			}
    164 		}
    165 		for (i = 0; i < n; i++)
    166 			cout << ans[i] << (i == n - 1 ? '\n' : ' ');
    167 
    168 		num = 1, last = 0;
    169 		for (i = 0; i < n; i++)
    170 		{
    171 			if (i == n - 1 || s[i] == '<')
    172 			{
    173 				for (j = i; j >= last; j--)
    174 					ans[j] = num++;
    175 				last = i + 1;
    176 			}
    177 		}
    178 		for (i = 0; i < n; i++)
    179 			cout << ans[i] << (i == n - 1 ? '\n' : ' ');
    180 	}
    181 }
    182 ```
    183 
    184 [1304E — 1-Trees and Queries](https://codeforces.com/contest/1304/problem/E)
    185 
    186 **Tutorial**
    187 
    188 Tutorial is loading...
    189 
    190 **Solution**
    191 
    192 ```
    193 #include <bits/stdc++.h>
    194 using namespace std;
    195 
    196 const int MAX_N = 100000;
    197 const int LIM = 17;
    198 const int INF = (int)1e9 + 7;
    199 
    200 vector<int> adj[MAX_N + 5];
    201 int depth[MAX_N + 5];
    202 int par[MAX_N + 5][LIM + 1];
    203 
    204 void build(int cur, int p)
    205 {
    206 	int i;
    207 
    208 	depth[cur] = depth[p] + 1;
    209 	par[cur][0] = p;
    210 	for (i = 1; i <= LIM; i++)
    211 		par[cur][i] = par[par[cur][i - 1]][i - 1];
    212 
    213 	for (int x : adj[cur])
    214 		if (x != p)
    215 			build(x, cur);
    216 }
    217 
    218 int lca_len(int a, int b)
    219 {
    220 	int i, len = 0;
    221 
    222 	if (depth[a] > depth[b])
    223 		swap(a, b);
    224 	for (i = LIM; i >= 0; i--)
    225 	{
    226 		if (depth[par[b][i]] >= depth[a])
    227 		{
    228 			b = par[b][i];
    229 			len += (1 << i);
    230 		}
    231 	}
    232 	
    233 	if (a == b)
    234 		return len;
    235 	for (i = LIM; i >= 0; i--)
    236 	{
    237 		if (par[a][i] != par[b][i])
    238 		{
    239 			a = par[a][i];
    240 			b = par[b][i];
    241 			len += (1 << (i + 1));
    242 		}
    243 	}
    244 	return len + 2;
    245 }
    246 
    247 int main()
    248 {
    249 	ios::sync_with_stdio(false);
    250 	cin.tie(0);
    251 
    252 	int n, q, i;
    253 	cin >> n;
    254 	
    255 	for (i = 0; i < n - 1; i++)
    256 	{
    257 		int u, v;
    258 		cin >> u >> v;
    259 		adj[u].push_back(v);
    260 		adj[v].push_back(u);
    261 	}
    262 	build(1, 0);
    263 
    264 	cin >> q;
    265 	while (q--)
    266 	{
    267 		int x, y, a, b, k;
    268 		cin >> x >> y >> a >> b >> k;
    269 		int without = lca_len(a, b);
    270 		int with = min(lca_len(a, x) + lca_len(y, b), lca_len(a, y) + lca_len(x, b)) + 1;
    271 		int ans = INF;
    272 		if (without % 2 == k % 2)
    273 			ans = without;
    274 		if (with % 2 == k % 2)
    275 			ans = min(ans, with);
    276 		cout << (ans <= k ? "YES" : "NO") << '\n';
    277 	}
    278 }
    279 ```
    280 
    281 [1304F1 — Animal Observation (easy version)](https://codeforces.com/contest/1304/problem/F1)
    282 
    283 **Tutorial**
    284 
    285 Tutorial is loading...
    286 
    287 **Solution**
    288 
    289 ```
    290 #include <bits/stdc++.h>
    291 using namespace std;
    292 
    293 const int MAX_N = 50;
    294 const int MAX_M = 20000;
    295 const int MAX_K = 20;
    296 
    297 int animal[MAX_N + 5][MAX_M + 5];
    298 int psum[MAX_N + 5][MAX_M + 5];
    299 int lmax[MAX_N + 5][MAX_M + 5];
    300 int rmax[MAX_N + 5][MAX_M + 5];
    301 int dp[MAX_N + 5][MAX_M + 5];
    302 
    303 inline int ps(int i, int j, int k)
    304 {
    305 	return psum[i][k] - psum[i][j - 1];
    306 }
    307 
    308 int main()
    309 {
    310 	ios::sync_with_stdio(false);
    311 	cin.tie(0);
    312 	int i, j;
    313 
    314 	int n, m, k;
    315 	cin >> n >> m >> k;
    316 	for (i = 1; i <= n; i++)
    317 	{
    318 		for (j = 1; j <= m; j++)
    319 		{
    320 			cin >> animal[i][j];
    321 			psum[i][j] = psum[i][j - 1] + animal[i][j];
    322 		}
    323 	}
    324 
    325 	for (i = 1; i <= n; i++)
    326 	{
    327 		for (j = 1; j <= m - k + 1; j++)
    328 		{
    329 			int p = ps(i, j, j + k - 1) + ps(i + 1, j, j + k - 1);
    330 			if (i == 1)
    331 			{
    332 				dp[i][j] = p;
    333 				continue;
    334 			}
    335 			int mx = 0;
    336 			for (int x = max(1, j - k + 1); x <= min(m - k + 1, j + k - 1); x++)
    337 				mx = max(mx, dp[i - 1][x] + p - ps(i, max(x, j), min(x + k - 1, j + k - 1)));
    338 			dp[i][j] = mx;
    339 			if (j > k)
    340 				dp[i][j] = max(dp[i][j], lmax[i - 1][j - k] + p);
    341 			if (j + k - 1 <= m - k)
    342 				dp[i][j] = max(dp[i][j], rmax[i - 1][j + k] + p);
    343 		}
    344 		for (j = 1; j <= m - k + 1; j++)
    345 			lmax[i][j] = max(lmax[i][j - 1], dp[i][j]);
    346 		for (j = m - k + 1; j >= 1; j--)
    347 			rmax[i][j] = max(rmax[i][j + 1], dp[i][j]);
    348 	}
    349 
    350 	cout << *max_element(dp[n] + 1, dp[n] + m + 1) << '\n';
    351 }
    352 ```
    353 
    354 [1304F2 — Animal Observation (hard version)](https://codeforces.com/contest/1304/problem/F2)
    355 
    356 **Tutorial**
    357 
    358 Tutorial is loading...
    359 
    360 **Solution: O(nmlogm)**
    361 
    362 ```
    363 #include <bits/stdc++.h>
    364 using namespace std;
    365 
    366 const int MAX_N = 50;
    367 const int MAX_M = 20000;
    368 const int MAX_K = 20;
    369 
    370 int animal[MAX_N + 5][MAX_M + 5];
    371 int psum[MAX_N + 5][MAX_M + 5];
    372 int dp[MAX_N + 5][MAX_M + 5];
    373 int t[MAX_M * 4], lazy[MAX_M * 4];
    374 
    375 void update_lazy(int i, int lo, int hi)
    376 {
    377 	if (lazy[i])
    378 	{
    379 		t[i] += lazy[i];
    380 		if (lo != hi)
    381 		{
    382 			lazy[i * 2] += lazy[i];
    383 			lazy[i * 2 + 1] += lazy[i];
    384 		}
    385 		lazy[i] = 0;
    386 	}
    387 }
    388 
    389 int update(int i, int lo, int hi, int l, int r, int val)
    390 {
    391 	update_lazy(i, lo, hi);
    392 	if (lo > r || hi < l)
    393 		return t[i];
    394 	if (l <= lo && hi <= r)
    395 	{
    396 		t[i] += val;
    397 		if (lo != hi)
    398 		{
    399 			lazy[i * 2] += val;
    400 			lazy[i * 2 + 1] += val;
    401 		}
    402 		return t[i];
    403 	}
    404 	int mid = (lo + hi) / 2;
    405 	return t[i] = max(update(i * 2, lo, mid, l, r, val), update(i * 2 + 1, mid + 1, hi, l, r, val));
    406 }
    407 
    408 int main()
    409 {
    410 	ios::sync_with_stdio(false);
    411 	cin.tie(0);
    412 	int i, j;
    413 
    414 	int n, m, k;
    415 	cin >> n >> m >> k;
    416 	for (i = 1; i <= n; i++)
    417 	{
    418 		for (j = 1; j <= m; j++)
    419 		{
    420 			cin >> animal[i][j];
    421 			psum[i][j] = psum[i][j - 1] + animal[i][j];
    422 		}
    423 	}
    424 
    425 	int mm = m - k + 1;
    426 
    427 	for (i = 1; i <= mm; i++)
    428 		dp[1][i] = psum[1][i + k - 1] - psum[1][i - 1] + psum[2][i + k - 1] - psum[2][i - 1];
    429 	for (i = 2; i <= n; i++)
    430 	{
    431 		memset(t, 0, sizeof t);
    432 		memset(lazy, 0, sizeof lazy);
    433 		for (j = 1; j <= mm; j++)
    434 			update(1, 1, mm, j, j, dp[i - 1][j]);
    435 		for (j = 1; j <= k; j++)
    436 			update(1, 1, mm, 1, j, -animal[i][j]);
    437 		for (j = 1; j <= mm; j++)
    438 		{
    439 			dp[i][j] = t[1] + psum[i][j + k - 1] - psum[i][j - 1] + psum[i + 1][j + k - 1] - psum[i + 1][j - 1];
    440 			if (j != mm)
    441 			{
    442 				update(1, 1, mm, max(1, j - k + 1), j, animal[i][j]);
    443 				update(1, 1, mm, j + 1, j + k, -animal[i][j + k]);
    444 			}
    445 		}
    446 	}
    447 
    448 	cout << *max_element(dp[n] + 1, dp[n] + mm + 1) << endl;
    449 }
    450 ```
    451 
    452 **Solution: O(nm)**
    453 
    454 ```
    455 #include <bits/stdc++.h>
    456 using namespace std;
    457 using pii = pair<int, int>;
    458 using vi = vector<int>;
    459 using vvi = vector<vi>;
    460 
    461 const int MAX_N = 50;
    462 const int MAX_M = 20000;
    463 const int MAX_K = 20;
    464 
    465 int n, m, k;
    466 
    467 inline int ps(vvi &p, int i, int s, int e)
    468 {
    469 	if (s < 1)
    470 		return p[i][e];
    471 	return p[i][e] - p[i][s - 1];
    472 }
    473 
    474 void calc_overlapped(vvi &ar, vvi &p, vvi &dp, int i)
    475 {
    476 	int j;
    477 	deque<pii> dq;
    478 	for (j = 1; j <= m - k + 1; j++)
    479 	{
    480 		int num = dp[i - 1][j] - ps(p, i, j, j + k - 1);
    481 		if (dq.size() && dq.front().second <= j - k)
    482 			dq.pop_front();
    483 		while (dq.size() && dq.back().first + ps(p, i, dq.back().second, j - 1) <= num)
    484 			dq.pop_back();
    485 		dq.push_back({ num, j });
    486 		dp[i][j] = dq.front().first + ps(p, i, dq.front().second, j - 1) + ps(p, i, j, j + k - 1) + ps(p, i + 1, j, j + k - 1);
    487 	}
    488 }
    489 
    490 int main()
    491 {
    492 	ios::sync_with_stdio(false);
    493 	cin.tie(0);
    494 	int i, j;
    495 
    496 	cin >> n >> m >> k;
    497 
    498 	vvi init(n + 5, vi(m + 5, 0));
    499 	vvi animal, animal_rev, psum, psum_rev, lmax, rmax, dp, dpl, dpr;
    500 	animal = animal_rev = psum = psum_rev = lmax = rmax = dp = dpl = dpr = init;	
    501 
    502 	for (i = 1; i <= n; i++)
    503 	{
    504 		for (j = 1; j <= m; j++)
    505 		{
    506 			cin >> animal[i][j];
    507 			psum[i][j] = psum[i][j - 1] + animal[i][j];
    508 			animal_rev[i][m - j + 1] = animal[i][j];
    509 		}
    510 		for (j = 1; j <= m; j++)
    511 			psum_rev[i][j] = psum_rev[i][j - 1] + animal_rev[i][j];
    512 	}
    513 
    514 	deque<pii> dq;
    515 	for (i = 1; i <= n; i++)
    516 	{
    517 		for (j = 1; j <= m - k + 1; j++)
    518 		{
    519 			if (j > k)
    520 				dp[i][j] = lmax[i - 1][j - k];
    521 			if (j <= m - k * 2 + 1)
    522 				dp[i][j] = max(dp[i][j], rmax[i - 1][j + k]);
    523 			dp[i][j] += ps(psum, i, j, j + k - 1) + ps(psum, i + 1, j, j + k - 1);
    524 		}
    525 
    526 		calc_overlapped(animal, psum, dpl, i);
    527 		calc_overlapped(animal_rev, psum_rev, dpr, i);
    528 
    529 		for (j = 1; j <= m - k + 1; j++)
    530 		{
    531 			dp[i][j] = max({ dp[i][j], dpl[i][j], dpr[i][m - j - k + 2] });
    532 			dpl[i][j] = dpr[i][m - j - k + 2] = dp[i][j];
    533 		}
    534 			
    535 		for (j = 1; j <= m - k + 1; j++)
    536 			lmax[i][j] = max(lmax[i][j - 1], dp[i][j]);
    537 		for (j = m - k + 1; j >= 1; j--)
    538 			rmax[i][j] = max(rmax[i][j + 1], dp[i][j]);
    539 	}
    540 
    541 	cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
    542 }
    543 ```