Skip to content

Instantly share code, notes, and snippets.

@alexkay
Created January 12, 2012 14:11
Show Gist options
  • Save alexkay/1600725 to your computer and use it in GitHub Desktop.
Save alexkay/1600725 to your computer and use it in GitHub Desktop.
Code Sprint 2 - Subsequence Weighting
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment