LA 5780 - The Agency

LA5780.cpp

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define foreach(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)

vector<int> up, down, eq;
long long sumon;

long long solve(int k) {
    long long sump = sumon;
    int i=0, j=0;
    long long ans = 0;
    while(i<k and j<down.size()) {
        if(eq[i]>down[j])
            sump -= eq[i++];
        else
            sump -= down[j++];
        ans += sump;
    }
    while(i<k) {
        sump -= eq[i++];
        ans += sump;
    }
    while(j<down.size()) {
        sump -= down[j++];
        ans += sump;
    }
    i--;
    j = 0;
    while(i>=0 and j<up.size()) {
        if(eq[i]<=up[j])
            sump += eq[i--];
        else
            sump += up[j++];
        ans += sump;
    }
    while(i>=0) {
        sump += eq[i--];
        ans += sump;
    }
    while(j<up.size()) {
        sump += up[j++];
        ans += sump;
    }
    //printf("# %d: %lld %lld\n", k, ans, sumon);
    return ans;
}

int main() {
    int n, t, caso = 0;
    string a, b;
    while(scanf("%d", &n)!=EOF and n) {
        eq.clear();
        down.clear();
        up.clear();
        cin>>a>>b;
        for(int i=0; i<n; i++)
            a[i] -= '0', b[i] -= '0';
        sumon = 0;
        for(int i=0; i<n; i++) {
            scanf("%d", &t);
            if(a[i]) {
                if(b[i])
                    eq.push_back(t);
                else
                    down.push_back(t);
                sumon += t;
            }
            else if(b[i])
                up.push_back(t);
        }
        long long ans = 0x7fffffffffffffff, ca;
        sort(eq.rbegin(), eq.rend());
        sort(down.rbegin(), down.rend());
        sort(up.begin(), up.end());
        for(int i=0; i<=eq.size(); ++i) {
            if((ca=solve(i))<ans)
                ans = ca;
            else
                break;
        }
        printf("Case %d: %lld\n", ++caso, ans);
    }
}