Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
for (int i = 0; i < t; ++i) {
int a, b, k;
cin >> a >> b >> k;
cout << (a - b) * 1ll * (k / 2) + a * (k & 1) << endl;
}
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans = 0;
for (int i = 1; i < n - 1; ++i) {
if (a[i] == 0 && a[i - 1] == 1 && a[i + 1] == 1) {
++ans;
a[i + 1] = 0;
}
}
cout << ans << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
vector<int> a(n);
vector<int> cnt(MAX + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
++cnt[a[i]];
}
long long sum = accumulate(a.begin(), a.end(), 0ll);
vector<int> ans;
for (int i = 0; i < n; ++i) {
sum -= a[i];
--cnt[a[i]];
if (sum % 2 == 0 && sum / 2 <= MAX && cnt[sum / 2] > 0) {
ans.push_back(i);
}
sum += a[i];
++cnt[a[i]];
}
cout << ans.size() << endl;
for (auto it : ans) cout << it + 1 << " ";
cout << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200 * 1000 + 1;
int n, k;
vector<int> s, t;
vector<int> cnts(MAX);
bool can(int cnt) {
t.clear();
for (int i = 0; i < MAX; ++i) {
int need = min(cnts[i] / cnt, k - int(t.size()));
for (int j = 0; j < need; ++j) {
t.push_back(i);
}
}
return int(t.size()) == k;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> k;
s = vector<int>(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
for (auto c : s) {
++cnts[c];
}
int l = 0, r = n;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (can(mid)) {
l = mid;
} else {
r = mid;
}
}
if (!can(r)) can(l);
for (auto it : t) cout << it << " ";
cout << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n;
cin >> n;
map<int, int> cnt;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
++cnt[x];
}
vector<int> cnts;
for (auto it : cnt) {
cnts.push_back(it.second);
}
sort(cnts.begin(), cnts.end());
int ans = 0;
for (int i = 1; i <= cnts.back(); ++i) {
int pos = int(cnts.size()) - 1;
int cur = i;
int res = cur;
while (cur % 2 == 0 && pos > 0) {
cur /= 2;
--pos;
if (cnts[pos] < cur) break;
res += cur;
}
ans = max(ans, res);
}
cout << ans << endl;
return 0;
}
1077F1 - Pictures with Kittens (easy version)
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
const long long INF64 = 1e18;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, k, x;
cin >> n >> k >> x;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<vector<long long>> dp(n + 1, vector<long long>(x + 1, -INF64));
dp[0][x] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < x; ++j) {
for (int p = 1; p <= k; ++p) {
if (i - p < 0) break;
if (dp[i - p][j + 1] == -INF64) {
continue;
}
dp[i][j] = max(dp[i][j], dp[i - p][j + 1] + a[i - 1]);
}
}
}
long long ans = -INF64;
for (int i = n - k + 1; i <= n; ++i) {
ans = max(ans, *max_element(dp[i].begin(), dp[i].end()));
}
if (ans == -INF64) ans = -1;
cout << ans << endl;
return 0;
}
1077F2 - Pictures with Kittens (hard version)
Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp make_pair
typedef long long li;
typedef pair<li, li> pll;
const li INF64 = 1e18;
struct myQueue {
stack<pll> s1, s2;
int size() {
return s1.size() + s2.size();
}
bool isEmpty() {
return size() == 0;
}
long long getMax() {
if (isEmpty()) {
return -INF64;
}
if (!s1.empty() && !s2.empty()) {
return max(s1.top().y, s2.top().y);
}
if (!s1.empty()) {
return s1.top().y;
}
return s2.top().y;
}
void push(long long val) {
if (s2.empty()) {
s2.push(mp(val, val));
} else {
s2.push(mp(val, max(val, s2.top().y)));
}
}
void pop() {
if (s1.empty()) {
while (!s2.empty()) {
if (s1.empty()) {
s1.push(mp(s2.top().x, s2.top().x));
} else {
s1.push(mp(s2.top().x, max(s2.top().x, s1.top().y)));
}
s2.pop();
}
}
assert(!s1.empty());
s1.pop();
}
};
int n, k, x;
vector<int> a;
vector<myQueue> q;
vector<queue<int>> pos;
vector<vector<long long>> dp;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> k >> x;
a = vector<int>(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
q = vector<myQueue>(x + 1);
pos = vector<queue<int>>(x + 1);
dp = vector<vector<long long>>(n + 1, vector<long long>(x + 1, -INF64));
dp[0][x] = 0;
pos[x].push(-1);
q[x].push(0ll);
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= x; ++j) {
while (!pos[j].empty() && pos[j].front() < i - k - 1) {
q[j].pop();
pos[j].pop();
}
}
for (int j = 0; j < x; ++j) {
if (!q[j + 1].isEmpty()) {
dp[i][j] = max(dp[i][j], q[j + 1].getMax() + a[i - 1]);
q[j].push(dp[i][j]);
pos[j].push(i - 1);
}
}
}
long long ans = -INF64;
for (int i = n - k + 1; i <= n; ++i) {
ans = max(ans, *max_element(dp[i].begin(), dp[i].end()));
}
if (ans == -INF64) ans = -1;
cout << ans << endl;
return 0;
}