マスコット改造した

見ればネタわかる人にはわかるマイナーチェンジ

2392

最初はソートしなくてもいいかな〜ってやってみたけどダメそうだったのでソートしてAC
ソートしないとできないのはまぁ考えると自明

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct block { int a, h, c; };
bool comp(const block& a, const block& b) {
    return a.a<b.a;
}
int k;
int dp[40001];
block b[400];
int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d",&k);
    for (int i=0; i<k; i++) scanf("%d%d%d",&b[i].h,&b[i].a,&b[i].c);
    sort(b, b+k, comp);
    int res=b[k-1].a;
    dp[0]=0;
    for (int i=0; i<k; i++) {
        for (int j=0; j<=b[i].a; j++) {
            if (dp[j]>=0) dp[j]=b[i].c;
            else if (j<b[i].h||dp[j-b[i].h]<=0) dp[j]=-1;
            else dp[j]=dp[j-b[i].h]-1;
            // printf("%d%c",dp[j],j==b[i].a?'\n':' ');
        }
    }
    // for (int i=0; i<=res; i++) printf("%d%c",dp[i],i%10==0?'\n':' ');
    while (dp[res]<0) res--;
    printf("%d\n",res);
}

3268

問題的にワーシャルフロイドかなぁって軽く考えてたらTLEしてdjkstraで通した。
ただの単一始点最短路の和の最大値

#include <cstdio>
#include <vector>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
struct edge {int to, cost;};
const int INF=100000;
int n, m, x, a, b, t;
vector<edge> G[1000];
int d[1000];
int djkstra(int s, int g) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+n, INF);
    d[s]=0;
    que.push(P(0,s));
    while (!que.empty()) {
        P p=que.top(); que.pop();
        int v=p.second;
        if (d[v]<p.first) continue;
        for (int i=0; i<G[v].size(); i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
    return d[g];
}
int main() {
    scanf("%d%d%d",&n,&m,&x);
    for (int i=0; i<m; i++) {
        scanf("%d%d%d",&a,&b,&t);
        G[a-1].push_back((edge){b-1,t});
    }
    int res=0;
    for (int i=0; i<n; i++) {
        res=max(res,djkstra(i,x-1)+djkstra(x-1,i));
    }
    printf("%d\n",res);
}

2395

全然題意が読めなくて、とりあえずサンプルの雰囲気的に最小全域木を構築したときに一番大きい辺の大きさを答える問題かなとおもってクラスカル書いたら普通にACした

#include <cstdio>
#include <algorithm>
using namespace std;
int par[2000], rank[2000];
void init(int n) {
    for (int i=0; i<n; i++) {
        par[i]=i;
        rank[i]=0;
    }
}
int find(int x) {
    if (par[x]==x) {
        return x;
    } else {
        return par[x]=find(par[x]);
    }
}
void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a==b) return;
    if (rank[a]<rank[b]) {
        par[a]=b;
    } else {
        par[b]=a;
        if (rank[a]==rank[b]) rank[a]++;
    }
}
bool same(int a, int b) {
    return find(a)==find(b);
}
struct edge { int u, v, cost; };
bool comp(const edge& a, const edge& b) {
    return a.cost<b.cost;
}
edge es[10000];
int N, M;
int main() {
    scanf("%d%d",&N,&M);
    for (int i=0; i<M; i++) scanf("%d%d%d",&es[i].u,&es[i].v,&es[i].cost);
    sort(es, es+M, comp);
    init(N);
    int res=0;
    for (int i=0; i<M; i++) {
        edge e=es[i];
        if (!same(e.u,e.v)) {
            unite(e.u,e.v);
            res=max(res,e.cost);
        }
    }
    printf("%d\n",res);
}