1519A - Красные и синие мармеладки
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val (r, b, d) = readLine()!!.split(' ').map { it.toInt() }
println(if (minOf(r, b) * (d + 1).toLong() >= maxOf(r, b)) "YES" else "NO")
}
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
fun main() {
repeat(readLine()!!.toInt()) {
val (n, m, k) = readLine()!!.split(' ').map { it.toInt() }
println(if (n * m - 1 == k) "YES" else "NO")
}
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
int main() {
int t;
scanf("%d", &t);
forn(_, t){
int n;
scanf("%d", &n);
vector<int> s(n), u(n);
forn(i, n){
scanf("%d", &s[i]);
--s[i];
}
forn(i, n){
scanf("%d", &u[i]);
}
vector<vector<int>> bst(n);
forn(i, n) bst[s[i]].push_back(u[i]);
forn(i, n) sort(bst[i].begin(), bst[i].end(), greater<int>());
vector<vector<long long>> pr(n, vector<long long>(1, 0));
forn(i, n) for (int x : bst[i]) pr[i].push_back(pr[i].back() + x);
vector<long long> ans(n);
forn(i, n) for (int k = 1; k <= int(bst[i].size()); ++k)
ans[k - 1] += pr[i][bst[i].size() / k * k];
forn(i, n)
printf("%lld ", ans[i]);
puts("");
}
return 0;
}
1519D - Максимальная сумма произведений
Идея: vovuh
Разбор
Tutorial is loading...
Решение (Neon)
#include <bits/stdc++.h>
using namespace std;
using li = long long;
int main() {
int n;
cin >> n;
vector<li> a(n), b(n);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
vector<li> pr(n + 1, 0);
for (int i = 0; i < n; ++i)
pr[i + 1] = pr[i] + a[i] * b[i];
li ans = pr[n];
for (int c = 0; c < n; ++c) {
li cur = a[c] * b[c];
for (int l = c - 1, r = c + 1; l >= 0 && r < n; --l, ++r) {
cur += a[l] * b[r];
cur += a[r] * b[l];
ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1]));
}
cur = 0;
for (int l = c, r = c + 1; l >= 0 && r < n; --l, ++r) {
cur += a[l] * b[r];
cur += a[r] * b[l];
ans = max(ans, cur + pr[l] + (pr[n] - pr[r + 1]));
}
}
cout << ans << endl;
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (awoo)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second
using namespace std;
struct point{
int a, b, c, d;
};
typedef pair<long long, long long> frac;
typedef pair<int, int> pt;
int n;
vector<point> a;
map<frac, int> sv;
frac norm(long long x, long long y){
long long g = __gcd(x, y);
return {x / g, y / g};
}
vector<vector<pt>> g;
vector<int> used;
vector<pt> ans;
int dfs(int v){
used[v] = 1;
int cur = -1;
for (auto it : g[v]){
int u = it.x;
int i = it.y;
if (used[u] == 1) continue;
int nw = i;
if (!used[u]){
int tmp = dfs(u);
if (tmp != -1){
ans.push_back({nw, tmp});
nw = -1;
}
}
if (nw != -1){
if (cur != -1){
ans.push_back({cur, nw});
cur = -1;
}
else{
cur = nw;
}
}
}
used[v] = 2;
return cur;
}
int main() {
scanf("%d", &n);
a.resize(n);
forn(i, n) scanf("%d%d%d%d", &a[i].a, &a[i].b, &a[i].c, &a[i].d);
g.resize(2 * n);
forn(i, n){
frac f1 = norm((a[i].a + a[i].b) * 1ll * a[i].d, a[i].b * 1ll * a[i].c);
frac f2 = norm(a[i].a * 1ll * a[i].d, a[i].b * 1ll * (a[i].c + a[i].d));
if (!sv.count(f1)){
int k = sv.size();
sv[f1] = k;
}
if (!sv.count(f2)){
int k = sv.size();
sv[f2] = k;
}
g[sv[f1]].push_back({sv[f2], i});
g[sv[f2]].push_back({sv[f1], i});
}
used.resize(sv.size());
forn(i, sv.size()) if (!used[i])
dfs(i);
printf("%d\n", int(ans.size()));
for (auto it : ans) printf("%d %d\n", it.x + 1, it.y + 1);
}
Идея: BledDest
Разбор
Tutorial is loading...
Решение (BledDest)
#include<bits/stdc++.h>
using namespace std;
const int N = 6;
const int M = 400;
const int INF = int(1e9);
int a[N];
int b[N];
int c[N][N];
int n, m;
struct state
{
vector<int> need;
int v2;
int v1;
int rem;
state() {};
state(vector<int> need, int v1, int v2, int rem) : need(need), v1(v1), v2(v2), rem(rem) {};
};
int get_code(const vector<int>& v)
{
int ans = 0;
for(int i = 0; i < v.size(); i++)
ans = ans * 5 + v[i];
return ans;
}
int get_code(const state& s)
{
int code = get_code(s.need);
code = code * 6 + s.v2;
code = code * 6 + s.v1;
code = code * 5 + s.rem;
return code;
}
vector<int> get_vector(int code, int n)
{
vector<int> res(n);
for(int i = n - 1; i >= 0; i--)
{
res[i] = code % 5;
code /= 5;
}
return res;
}
state get_state(int code)
{
int rem = code % 5;
code /= 5;
int v1 = code % 6;
code /= 6;
int v2 = code % 6;
code /= 6;
vector<int> need = get_vector(code, n);
return state(need, v1, v2, rem);
}
const int Z = 40 * int(1e6);
int dp[Z];
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < m; i++)
cin >> b[i];
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> c[i][j];
for(int i = 0; i < Z; i++)
dp[i] = INF;
state start(vector<int>(n, 0), 0, 0, 0);
int ans = INF;
dp[get_code(start)] = 0;
for(int i = 0; i < Z; i++)
{
if(dp[i] == INF) continue;
state s = get_state(i);
for(int f = 0; f <= 4; f++)
{
if(s.need[s.v1] + f > a[s.v1] || s.rem + f > b[s.v2])
continue;
int add = (f == 0 ? 0 : c[s.v1][s.v2]);
state nw = s;
nw.need[s.v1] += f;
nw.rem += f;
if(s.v1 == n - 1)
{
nw.v1 = 0;
nw.v2 = s.v2 + 1;
nw.rem = 0;
}
else
{
nw.v1 = s.v1 + 1;
}
if(nw.need == vector<int>(a, a + n))
ans = min(ans, dp[i] + add);
if(nw.v2 < m)
{
int code = get_code(nw);
dp[code] = min(dp[code], dp[i] + add);
}
}
}
if(ans == INF) ans = -1;
cout << ans << endl;
}