Code Sprint 2 - Subsequence Weighting

gistfile1.cpp

#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

struct Node {
    int a;
    long long w;
    Node *prev;
    Node *next;

    Node(int a, long long w): a(a), w(w), prev(NULL), next(NULL) {}
};

class ptr_less {
public:
    bool operator()(const Node *lhs, const Node *rhs) const {
        return lhs->a < rhs->a;
    }
};

typedef set<Node*, ptr_less> Tree;

int main()
{
    int C;
    cin >> C;
    for (int c = 0; c < C; c++) {
        int N;
        cin >> N;
        int *a = new int[N];
        int *w = new int[N];
        for (int i = 0; i < N; i++) {
            cin >> a[i];
        }
        for (int i = 0; i < N; i++) {
            cin >> w[i];
        }

        Tree tree;
        Node *plast = NULL;
        for (int i = 0; i < N; i++) {
            Node *pnode = new Node(a[i], w[i]);
            Tree::iterator it = tree.lower_bound(pnode);

            if (it == tree.end()) {
                tree.insert(pnode);
                if (plast) {
                    plast->next = pnode;
                    pnode->prev = plast;
                    pnode->w += plast->w;
                }
                plast = pnode;
            } else if ((*it)->a == pnode->a) {
                if ((*it)->prev) {
                    (*it)->w = max((*it)->w, pnode->w + (*it)->prev->w);
                } else {
                    (*it)->w = max((*it)->w, pnode->w);
                }
                delete pnode;
                pnode = *it;
            } else {
                tree.insert(pnode);
                Node *prev = (*it)->prev;
                (*it)->prev = pnode;
                pnode->next = *it;
                if (prev) {
                    pnode->prev = prev;
                    prev->next = pnode;
                    pnode->w += prev->w;
                }
            }
            while (pnode->next && pnode->next->w <= pnode->w) {
                Node *next = pnode->next;
                pnode->next = next->next;
                if (next->next) {
                    next->next->prev = pnode;
                }
                tree.erase(next);
                delete next;
            }
            if (!pnode->next) {
                plast = pnode;
            }
        }

        cout << plast->w << endl;
        for (Tree::iterator it = tree.begin(); it != tree.end(); it++) {
            delete *it;
        }

        delete[] w;
        delete[] a;
    }
    return 0;
}