IOI2009 "Salesman"

はじめてのあいおーあい。

ろくに確認もせずテストデータにとりあえず投げた結果玉砕し、その後しょーもないことで時間を潰した。

練習量が足りない。死にたい。

problem

IPSJの雑誌とテレビの両方で見かけたので解いてみようと思った。問題の名称がどう見てもTSP。

solution

IPSJのにはsegment treeって書いてあったけど所謂区間木じゃなくてBinaryIndexTreeの類だった。
ところでBinaryIndexTreeでググっても出てこないんだけど、この名称って間違ってるの？

source

#include <cstdio>
#include <climits>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>

#define MY_MIN (INT_MIN+500000000)

using namespace std;

int n,u,d,s;
struct fair {
    int id, t, l, m, msum, ms0, ms1;
    fair() : msum(MY_MIN) {}
    bool operator<(const fair& o) const {
        if(t!=o.t) return t<o.t;
        return l<o.l;
    }
};
struct bit {
    vector<int> prices;
    bit() : prices(1<<20, MY_MIN) {}
    void insert(int idx, int price) {
        for(int x = idx+(1<<19); x; x>>=1) {
            prices[x] = max(prices[x], price);
        }
    }
    int find_(int t) {
        if(t==0)return MY_MIN;
        int ret = find_(t>>1);
        if(t&1) {
            ret = max(ret, prices[t-1]);
        }
        return ret;
    }
    int find(int t) {
        return find_(t+(1<<19));
    }
};
vector<fair> fairs;

int main(int argc, char **argv)
{
    scanf("%d%d%d%d", &n, &u, &d, &s);
    fairs.resize(n+1);
    for(int i = 0; i < n; i++) {
        fairs[i].id = i;
        scanf("%d%d%d", &fairs[i].t, &fairs[i].l, &fairs[i].m);
    }
    fairs[n].id = -1;
    fairs[n].t = INT_MAX;
    fairs[n].l = s;
    fairs[n].m = 0;
    sort(fairs.begin(), fairs.end());
    bit b_upside, b_downside;
    b_upside.insert(500010-s, 0-u*s);
    b_downside.insert(s, 0+d*s);
    int i = 0;
    while(i<fairs.size()) {
        int is = fairs.size();
        for(int j = i; j < fairs.size(); j++) {
            if(fairs[i].t != fairs[j].t) {
                is = j;
                break;
            }
            fairs[j].msum = max(fairs[j].msum, b_upside.find(500010-fairs[j].l+1)+u*fairs[j].l);
            fairs[j].msum = max(fairs[j].msum, b_downside.find(fairs[j].l+1)-d*fairs[j].l);
        }
        for(int j = i; j < is; j++) {
            fairs[j].msum += fairs[j].m;
        }
        int current_max = MY_MIN;
        for(int j = i; j < is; j++) {
            fairs[j].ms0 = max(fairs[j].msum, current_max-d*fairs[j].l+fairs[j].m);
            current_max = fairs[j].ms0+d*fairs[j].l;
        }
        current_max = MY_MIN;
        for(int j = is-1; j >= i; j--) {
            fairs[j].ms1 = max(fairs[j].msum, current_max+u*fairs[j].l+fairs[j].m);
            current_max = fairs[j].ms1-u*fairs[j].l;
        }
        for(int j = i; j < is; j++) {
            fairs[j].msum = max(fairs[j].msum, fairs[j].ms0);
            fairs[j].msum = max(fairs[j].msum, fairs[j].ms1);
            b_upside.insert(500010-fairs[j].l, fairs[j].msum-u*fairs[j].l);
            b_downside.insert(fairs[j].l, fairs[j].msum+d*fairs[j].l);
        }
        i = is;
    }
    printf("%d\n", fairs[n].msum);
    return 0;
}