Topcoder SRM 588 div1

o-- でした。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define all(c) c.begin(),c.end()

struct Song{
    int dur;
    int tone;
    Song(int d,int t) : dur(d),tone(t) {}
    Song() {}
};

struct ToneComp{
    bool operator()(const Song& a,const Song& b){
        return a.tone < b.tone;
    }

};

struct DurComp{
    bool operator()(const Song& a,const Song& b){
        return a.dur > b.dur;
    }
};

ostream& operator<<(ostream& os,const Song& a){
    os << "(" << a.dur << "," << a.tone << ")";
    return os;
}

class GUMIAndSongsDiv1{
public:
    int maxSongs(vector <int> duration, vector <int> tone, int T){
        int N = duration.size();
        int ret = 0;
        vector<Song> s;
        for(int i=0;i<N;i++){
            s.push_back(Song(duration[i],tone[i]));
        }
        sort(all(s),ToneComp());

        for(int start=0;start<N;start++){
            for(int end=start;end<N;end++){
                vector<Song> sc(end-start+1);
                copy(s.begin()+start,s.begin()+end+1,sc.begin());
                int sum = abs(sc.front().tone - sc.back().tone);
                sort(all(sc),DurComp());
                for(int i=0;i<sc.size();i++){
                    sum += sc[i].dur;
                }
                int ind = 0;
                while(sum > T and ind != sc.size()){
                    sum -= sc[ind].dur;
                    ind++;
                }
                ret = max(ret,(int)sc.size()-ind);
            }
        }
        return ret;
    }
};

後で通しました。

#include <iostream>
#include <vector>
#include <utility>
#include <stack>
#include <set>

using namespace std;

struct State{
    int r,g,w,opened;
    State(int r,int g,int w,int opened) : r(r),g(g),w(w),opened(opened) {};
};

// O(2^N * N ?)
class KeyDungeonDiv1{
public:
    int maxKeys(vector <int> doorR, vector <int> doorG, vector <int> roomR,
                vector <int> roomG, vector <int> roomW, vector <int> keys){

        int ret = 0;
        int N = doorR.size();
        State start(keys[0],keys[1],keys[2],0);
        stack<State> sta;
        set<pair<int,int> > alr;
        sta.push(start);
        while(not sta.empty()){
            State now = sta.top();
            sta.pop();
            if(alr.find(make_pair(now.opened,now.w)) != alr.end()) continue;
            alr.insert(make_pair(now.opened,now.w));
            ret = max(ret,now.r+now.g+now.w);
            for(int i=0;i<N;i++){
                if((now.opened & (1 << i)) == 0){
                    State ne(now.r,now.g,now.w,(now.opened | (1 << i)));
                    if(doorR[i] > ne.r){
                        ne.w -= (doorR[i] - ne.r);
                        ne.r = 0;
                    }else{
                        ne.r -= doorR[i];
                    }
                    if(doorG[i] > ne.g){
                        ne.w -= (doorG[i] - ne.g);
                        ne.g = 0;
                    }else{
                        ne.g -= doorG[i];
                    }
                    if(ne.r >= 0 and ne.g >= 0 and ne.w >= 0){
                        ne.r += roomR[i];
                        ne.g += roomG[i];
                        ne.w += roomW[i];
                        sta.push(ne);
                    }
                }
            }
        }
        return ret;
    }
};