TCO11 Round1 Hard(1000) IPv444

IPv444

それぞれの列について、一度も出てきていない数字の集合を-1で表す。出てきた数字と-1を組み合わせて得られる表現は、高々51⁴個で、表すIPの個数が計算できて、同じ表現が分割されて売られることはない。各表現について、最高値を求める。

#include <string>
#include <vector>
#include <set>
using namespace std;

vector<string>split(string w,char s)
{
    vector<string>r;
    int p,n;
    for(p=0;n=w.find(s,p),n!=w.npos;p=n+1)
        r.push_back(w.substr(p,n-p));
    r.push_back(w.substr(p));
    return r;
}

class IPv444{public:
long long getMaximumMoney( vector <string> request, vector <int> price )
{
    int n = (int)request.size();

    vector<vector<int> > req;
    for ( int i=0; i<n; i++ )
    {
        vector<string> t = split(request[i],'.');
        req.push_back( vector<int>(4) );
        for ( int j=0; j<4; j++ )
            req[i][j] = t[j]!="*" ? atoi(t[j].c_str()) : -1;
    }

    set<int> C[4];
    for ( int i=0; i<4; i++ )
        C[i].insert(-1);
    for ( int i=0; i<n; i++ )
    for ( int j=0; j<4; j++ )
        C[j].insert(req[i][j]);

    long long ans = 0;

    for ( set<int>::iterator c0=C[0].begin(); c0!=C[0].end(); c0++ )
    for ( set<int>::iterator c1=C[1].begin(); c1!=C[1].end(); c1++ )
    for ( set<int>::iterator c2=C[2].begin(); c2!=C[2].end(); c2++ )
    for ( set<int>::iterator c3=C[3].begin(); c3!=C[3].end(); c3++ )
    {
        int p = 0;

        for ( int i=0; i<n; i++ )
            if ( ( *c0==req[i][0] || req[i][0]==-1 ) &&
                 ( *c1==req[i][1] || req[i][1]==-1 ) &&
                 ( *c2==req[i][2] || req[i][2]==-1 ) &&
                 ( *c3==req[i][3] || req[i][3]==-1 ) )
                p = max( p, price[i] );

        long long num = ( *c0!=-1 ? 1ll : 1000ll-C[0].size()+1 )
                      * ( *c1!=-1 ? 1ll : 1000ll-C[1].size()+1 )
                      * ( *c2!=-1 ? 1ll : 1000ll-C[2].size()+1 )
                      * ( *c3!=-1 ? 1ll : 1000ll-C[3].size()+1 );

        ans += p * num;
    }

    return ans;
}};