Thank you for participating!
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve() {
string s;
cin >> s;
if(s[0]+s[1]+s[2] == s[3]+s[4]+s[5]) {
cout << "YES" << endl;
}
else {
cout << "NO" << endl;
}
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
}
Idea: Errichto
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n; cin >> n;
vector<int> a(n);
int mn = INT_MAX, ans = 0;
for(int i = 0; i < n; ++i) {
cin >> a[i];
mn = min(mn, a[i]);
}
for(int i = 0; i < n; ++i) {
ans += a[i] - mn;
}
cout << ans << "\n";
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
int cost(string& a, string& b) {
int val = 0;
for(int i = 0; i < a.size(); ++i) {
val += abs(a[i] - b[i]);
}
return val;
}
int main() {
int t; cin >> t;
while(t--) {
int n, m; cin >> n >> m;
vector<string> s(n);
for(int i = 0; i < n; ++i) {
cin >> s[i];
}
int ans = INT_MAX;
for(int i = 0; i < n; ++i) {
for(int j = i + 1; j < n; ++j) {
ans = min(ans, cost(s[i], s[j]));
}
}
cout << ans << "\n";
}
}
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n, m;
cin >> n >> m;
int a[n][m];
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
cin >> a[i][j];
}
}
int mx = 0;
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
int now = 0;
int ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci--;
cj--;
}
ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci++;
cj--;
}
ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci--;
cj++;
}
ci = i, cj = j;
while(ci >= 0 && ci < n && cj >= 0 && cj < m)
{
now+=a[ci][cj];
ci++;
cj++;
}
now-=a[i][j]*3;
mx = max(mx, now);
}
}
cout << mx << endl;
}
int main() {
int t;
cin >> t;
while(t--)
{
solve();
}
}
Idea: mesanu
Tutorial
Tutorial is loading...
Solution
#include "bits/stdc++.h"
using namespace std;
int main() {
int t; cin >> t;
while(t--) {
int n, q; cin >> n >> q;
vector<long long> a(n), p(n);
for(int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a.rbegin(), a.rend());
for(int i = 0; i < n; ++i) {
p[i] = (i ? p[i - 1] : 0) + a[i];
}
while(q--) {
long long x; cin >> x;
int l = 1, r = n, ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(p[mid - 1] >= x) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << "\n";
}
}
}
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n, k;
cin >> n >> k;
int a[n];
map<int, int> mp;
for(int i = 0; i < n; i++)
{
cin >> a[i];
mp[a[i]]++;
}
vector<int> c;
for(auto x : mp)
{
if(x.second >= k)
{
c.push_back(x.first);
}
}
if(c.size() == 0)
{
cout << -1 << endl;
return;
}
sort(c.begin(), c.end());
int mx = 0;
int lans = c[0], rans = c[0];
int l = c[0];
for(int i = 1; i < c.size(); i++)
{
if(c[i]-1 == c[i-1])
{
if(c[i]-l > mx)
{
lans = l;
rans = c[i];
mx = c[i]-l;
}
}
else
{
l = c[i];
}
}
cout << lans << " " << rans << endl;
}
int main(int argc, char * argv[])
{
int t;
cin >> t;
while(t--)
{
solve();
}
}
1676G - White-Black Balanced Subtrees
Idea: MikeMirzayanov
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
void solve() {
int n;
cin >> n;
vector<int> child[n + 7];
for (int i = 2; i <= n; i++) {
int x;
cin >> x;
child[x].push_back(i);
}
string s;
cin >> s;
int res = 0;
function<int(int)> dp = [&] (int x) {
int bal = (s[x - 1] == 'B') ? -1 : 1;
if (child[x].empty()) {return bal;}
for (int i : child[x]) {
bal += dp(i);
}
if (bal == 0) {res++;}
return bal;
};
dp(1);
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
1676H1 - Maximum Crossings (Easy Version)
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
void solve() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] >= a[j]) {res++;}
}
}
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}
1676H2 - Maximum Crossings (Hard Version)
Idea: flamestorm
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
long long merge(int a[], int temp[], int left, int mid, int right) {
int i, j, k;
long long count = 0;
i = left;
j = mid;
k = left;
while ((i <= mid - 1) && (j <= right)) {
if (a[i] <= a[j]){
temp[k++] = a[i++];
} else {
temp[k++] = a[j++];
count += (mid - i);
}
}
while (i <= mid - 1)
temp[k++] = a[i++];
while (j <= right)
temp[k++] = a[j++];
for (i=left; i <= right; i++)
a[i] = temp[i];
return count;
}
long long mergeSort(int a[], int temp[], int left, int right){
int mid;
long long count = 0;
if (right > left) {
mid = (right + left)/2;
count = mergeSort(a, temp, left, mid);
count += mergeSort(a, temp, mid+1, right);
count += merge(a, temp, left, mid+1, right);
}
return count;
}
long long aInversion(int a[], int n) {
int temp[n];
return mergeSort(a, temp, 0, n - 1);
}
void solve() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
long long res = aInversion(a, n);
sort(a, a + n);
long long curr = 1;
for (int i = 1; i < n; i++) {
if (a[i] != a[i - 1]) {res += (curr * (curr - 1)) / 2; curr = 1;}
else {curr++;}
}
res += (curr * (curr - 1)) / 2;
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}