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