JOI2015本選-4(8点).cpp

#include <bits/stdc++.h>
using namespace std;

#define times(n, i) uptil(0, n, i)
#define upto(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f); i <= _##i; i++)
#define uptil(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f); i < _##i; i++)
#define downto(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f); i >= _##i; i--)
#define downtil(f, t, i) for(auto _##i = (t), i = decltype(_##i)(f); i > _##i; i--)
#define unless(c) if(!(c))
#define until(c) while(!(c))
#define loop while(true)

long long calc(const vector<long long>& good){
    #ifndef EVAL
        cout << "\tcalc\n";
    #endif
    queue<long long> pyon;
    for(auto g : good) pyon.push(g);
    loop{
        int a = pyon.front(); pyon.pop();
        if(pyon.empty()) return a;
        int b = pyon.front(); pyon.pop();
        int c = pyon.front(); pyon.pop();
        #ifndef EVAL
            cout << "\t(" << a << ", " << b << ", " << c << " - " << a + b + c - max({a, b, c}) - min({a, b, c}) << ")\n";
        #endif
        pyon.push(a + b + c - max({a, b, c}) - min({a, b, c}));
    }
}

long long pyon(vector<long long>& good, vector<long long>& rest){
    #ifndef EVAL
        cout << "pyon(";
        for(auto x : good) cout << x << " ";
        cout << ", ";
        for(auto x : rest) cout << x << " ";
        cout << ")\n";
    #endif
    if(rest.empty()) return calc(good);
    long long ret = 0;
    for(auto& g : good){
        if(g == -1){
            auto g_ = g;
            g = rest.back();
            rest.pop_back();
            ret = max(ret, pyon(good, rest));
            rest.push_back(g);
            g = g_;
        }
    }
    #ifndef EVAL
        cout << " => " << ret << endl;
    #endif
    return ret;
}

int main(){
    int N, M;
    cin >> N >> M;
    vector<long long> good(N, -1);
    vector<long long> rest(N - M);
    times(M, i){
        int D, P;
        cin >> D >> P;
        P--;
        good[P] = D;
    }
    times(N - M, i){
        cin >> rest[i];
    }
    #ifndef EVAL
        times(N, i) cout << good[i] << " ";
        cout << endl;
    #endif
    cout << pyon(good, rest) << endl;
    return 0;
}