基礎勉強に勤しんでるにゃん

ツイートに流れる部分はにゃんしばり続けたほうがいいかなって思って・・・

PKU 3169

結局あり本の解説ガン見してた。
普通に難しい・・・

#include <cstdio>
#include <climits>
#include <algorithm>
#define inf INT_MAX/2
using namespace std;
int d[1000];
int n,ml,md;
int al[10000], bl[10000], dl[10000];
int ad[10000], bd[10000], dd[10000];
int main() {
    scanf("%d%d%d",&n,&ml,&md);
    fill(d, d+n, inf);
    d[0]=0;
    for (int i=0; i<ml; i++) {
        scanf("%d%d%d",&al[i],&bl[i],&dl[i]);
    }
    for (int i=0; i<md; i++) {
        scanf("%d%d%d",&ad[i],&bd[i],&dd[i]);
    }
    for (int k=0; k<n; k++) {
        for (int i=0; i+1<n; i++) {
            if (d[i+1]<inf) d[i]=min(d[i], d[i+1]);
        }
        for (int i=0; i<ml; i++) {
            if (d[al[i]-1]<inf) {
                d[bl[i]-1]=min(d[bl[i]-1],d[al[i]-1]+dl[i]);
            }
        }
        for (int i=0; i<md; i++) {
            if (d[bd[i]-1]<inf) {
                d[ad[i]-1]=min(d[ad[i]-1],d[bd[i]-1]-dd[i]);
            }
        }
    }
    int res=d[n-1];
    if (d[0]<0) {
        res=-1;
    } else if (res==inf) {
        res=-2;
    }
    printf("%d\n",res);
}

PKU 1064

全部からlを抜き出さなければとかいみわかんない制約つけてしまって1WA

#include <cstdio>
#include <cmath>
using namespace std;
int n, k;
double l[10000];
bool C(double x) {
    int cnt=0;
    for (int i=0; i<n; i++) {
        cnt+=int(l[i]/x);
    }
    return cnt>=k;
}
int main() {
    scanf("%d%d",&n,&k);
    for (int i=0; i<n; i++) scanf("%lf",&l[i]);
    double lb=0.0, ub=100001.0;
    for (int i=0; i<100; i++) {
        double mid=(lb+ub)/2;
        if (C(mid)) {
            lb=mid;
        } else {
            ub=mid;
        }
    }
    printf("%.2f\n",floor(ub*100)/100);
}

AOJ 0563

真ん中のとり方わかんなかった・・・
kagamizさんのみてなるほどなーって書いたorz

#include <cstdio>
#include <cmath>
#include <climits>
#include <algorithm>
using namespace std;
typedef long long ll;
struct elem {
    ll x, y;
};
int w, h, n;
elem e[100000];
ll x[100000], y[100000];
ll px[3], py[3];
int main() {
    scanf("%d%d%d",&w,&h,&n);
    for (int i=0; i<n; i++) {
        scanf("%lld%lld",&x[i],&y[i]);
        e[i]=(elem){x[i],y[i]};
    }
    sort(x, x+n);
    sort(y, y+n);
    px[0]=x[(n-1)/2];
    px[1]=x[(n+1)/2];
    py[0]=y[(n-1)/2];
    py[1]=y[(n+1)/2];
    ll res=LLONG_MAX, rx=0, ry=0;
    for (int i=0; i<2; i++) {
        for (int j=0; j<2; j++) {
            ll calc=0, m=0;
            for (int k=0; k<n; k++) {
                ll temp=(abs(px[i]-e[k].x)+abs(py[j]-e[k].y));
                m=max(m, temp);
                calc+=temp;
            }
            if (res>calc*2-m) {
                res=calc*2-m;
                rx=px[i]; ry=py[j];
            }
        }
    }
    printf("%lld\n%lld %lld\n",res,rx,ry);
}