1059

Misaka_9982
kankan
zy23

Naive_512

misaka_mikoto
Big_Tortoise
CipherTri

Misaka御坂
Jackyc

fanh
Avakos

xjc008
Коммунистический

Xinqwq

1个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10;

int n;
priority_queue <int, vector <int>, greater <int> > heap;
int ans;

int main()
{
scanf("%d", &n);
while (n --)
{
int v;
cin >> v;
heap.push(v);
}

while (heap.size() > 1)
{
auto a = heap.top();

heap.pop();

auto b = heap.top();

heap.pop();

ans += (a + b);

heap.push(a + b);
}

printf("%d\n", ans);

return 0;
}


1个月前
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
typedef pair <int, int> pii;

const int N = 5e4 + 10;
int n;
pii num[N];
int ans = -1e9;

int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++)
{
int w, s;
cin >> w >> s;
num[i] = {w + s, w};
}

sort(num, num + n);

for (int i = 0, sum = 0; i < n; i ++)
{
int w = num[i].y;
int s = num[i].x - w;
ans = max(ans, sum - s);
sum += w;
}

printf("%d\n", ans);

return 0;
}


1个月前
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int n;
int num[N];
int sum;
ll ans;

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &num[i]);

sort(num + 1, num + n + 1);

int sum = num[n + 1 >> 1];

for (int i = 1; i <= n; i++) ans += abs(num[i] - sum);

printf("%lld\n", ans);

return 0;
}


1个月前
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
int n;
int num[N];
ll ans;

int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &num[i]);

sort(num + 1, num + n + 1);

for (int i = 1; i <= n - 1; i ++) ans += num[i] * (n - i);

printf("%lld\n", ans);

return 0;
}


1个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n;

struct Range
{
int l, r;
bool operator <(const Range& W) const
{
return l < W.l;
}
}range[N];

int main()
{
cin >> n;
for (int i = 0; i < n; i ++)
{
int l, r;
cin >> l >> r;
range[i] = {l, r};
}

sort(range, range + n);

priority_queue <int, vector <int>, greater <int> > heap;

for (int i = 0; i < n; i ++)
{
auto r = range[i];

if (heap.empty() || heap.top() >= r.l) heap.push(r.r);
else
{
heap.pop();
heap.push(r.r);
}
}

cout << heap.size() << endl;

return 0;
}


1个月前
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;
#define x first
#define y second

int n;
vector <pii> interval;
int ed = -1e9 - 10;
int ans;

bool cmp(pii a, pii b)
{
return a.y < b.y;
}

int main()
{
cin >> n;
while (n --)
{
int l, r;
cin >> l >> r;

interval.push_back({l, r});
}

sort(interval.begin(), interval.end(), cmp);

for (auto item : interval)
{
if (ed < item.x)
{
ans ++;
ed = item.y;
}
}

cout << ans << endl;

return 0;
}


1个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n;
bool success = false;
int ans;

struct Range
{
int l, r;
bool operator < (const Range& W) const
{
return l < W.l;
}
}range[N];

int main()
{
int st, ed;
cin >> st >> ed;
cin >> n;
for (int i = 0; i < n; i ++)
{
int l, r;
cin >> l >> r;
range[i] = {l, r};
}

sort(range, range + n);

for (int i = 0; i < n; i++)
{
int j = i;
int r = -2e9;

while (j < n && range[j].l <= st)
{
r = max(r, range[j].r);
j ++;
}
if (r < st)
{
ans = -1;

break;
}

ans ++;

if (r >= ed)
{
success = true;

break;
}

st = r;
i = j - 1;
}

if (! success) ans = -1;

cout << ans << endl;

return 0;
}


1个月前
#include<bits/stdc++.h>

using namespace std;

const int N = 110;
int g[N][N];
int n;
int dist[N];
bool str[N];

int prim()
{
int res = 0;

memset(dist, 0x3f, sizeof dist);

dist[1]=0;

for (int i = 1; i <= n; i ++)
{
int t = -1;

for (int j = 1; j <= n; j ++) if (! str[j] && (t == -1 || dist[t] > dist[j])) t=j;

res += dist[t];
str[t] = true;

for (int j = 1; j <= n; j ++) if (dist[j] > g[t][j]) dist[j] = g[t][j];
}

return res;
}

int main()
{
cin >> n;

for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) cin>>g[i][j];

cout << prim() << endl;

return 0;
}


1个月前
#include <bits/stdc++.h>

using namespace std;

int m, n;
int ans;
int x[1005], y[1005];
double a[1005];
double sum;

double d(int a, int b, int c, int d)
{
double x = c - a, y = d - b;
return sqrt(x * x + y * y);
}

int p[1000010];

struct Edge
{
int a, b;
double w;
Edge(int a, int b)
{
this -> a = a;
this -> b = b;

w = d(x[a], y[a], x[b], y[b]);
}

Edge() { }

bool operator < (const Edge &W) const
{
return w < W.w;
}
}edges[1000010];

int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);

return p[x];
}
void kruskal()
{
sort(edges + 1, edges + ans + 1);

for (int i = 1; i <= ans; i ++) p[i] = i;
for (int i = 1; i <= ans; i ++)
{
int a = find(edges[i].a), b = find(edges[i].b);

if (a != b)
{
p[a] = b;
sum = max(sum, edges[i].w);
}
}
}

int main()
{
cin >> m;
for (int i = 1; i <= m; i++) cin >> a[i];
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> x[i] >> y[i];

for (int j = 1; j <= i; j ++)
edges[++ ans] = Edge(i, j);
}

kruskal();

ans = 0;

for (int i = 1; i <= m; i ++) if (a[i] >= sum) ans ++;

cout << ans << endl;

return 0;
}


1个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 100;
int fa[N];
int n, m;
int k, t;
int s[N];
long long ans;

struct node
{
int x, y, w;
}edge[N];

bool cmp(node a, node b)
{
return a.w < b.w;
}
int find(int x)
{
return fa[x] == x ? x : fa[x] = find(fa[x]);
}

int main()
{
scanf("%d\n", &t);

while (t --)
{
scanf("%d\n", &n);

for (int i = 1; i < n; i ++) scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);
for (int i = 1; i <= n; i ++)
{
fa[i] = i;
s[i] = 1;
}

sort(edge + 1, edge + n, cmp);

ans = 0;

for (int i = 1;i < n;i ++)
{
int x = find(edge[i].x);
int y = find(edge[i].y);
int w = edge[i].w;

if (x == y) continue;

ans += (long long)(s[x] * s[y] - 1) * (w + 1);
fa[x] = y;
s[y] += s[x];
}

printf("%lld\n",ans);
}

return 0;
}