Submission #138215

#	Time	Username	Problem	Language	Result	Execution time	Memory
138215		evpipis	Olympiads (BOI19_olympiads)	C++11	100 / 100	185 ms	3160 KiB

olympiads

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int len = 503, inf = 1e9;
int mx[len], mine[len], who[len], score[10];
int par[len][len], sum[len][len], dp[len][10], best[len][10];
int n, k, c;

struct node{
    int opt;
    bitset<len> block, must;
    vector<int> extra; /// check what happens here

    node(bitset<len> bl, bitset<len> mu){
        block = bl;
        must = mu;
        /// assume that bl, mu are always valid sets

        // inits
        int rem = k-must.count();
        for (int j = 0; j < k; j++)
            score[j] = 0;
        for (int bit = 1; bit < (1<<k); bit++)
            mx[bit] = -inf, mine[bit] = 0;

        for (int i = 0; i < n; i++)
            if (must[i])
                for (int j = 0; j < k; j++)
                    score[j] = max(score[j], par[i][j]);
        for (int bit = 1; bit < (1<<k); bit++)
            for (int j = 0; j < k; j++)
                if (bit&(1<<j))
                    mine[bit] += score[j];

        for (int i = 0; i < n; i++){
            if (block[i]|must[i]) continue;

            for (int bit = 1; bit < (1<<k); bit++)
                if (sum[i][bit] > mx[bit])
                    mx[bit] = sum[i][bit], who[bit] = i;
        }

        // compute dp
        for (int bit = 1; bit < (1<<k); bit++){
            dp[bit][0] = -inf;
            for (int i = 1; i <= rem; i++){
                dp[bit][i] = -inf;
                for (int sub = bit; sub > 0; sub = (sub-1)&bit)
                    if (dp[bit-sub][i-1] != -inf && dp[bit-sub][i-1]+mx[sub] > dp[bit][i])
                        dp[bit][i] = dp[bit-sub][i-1]+mx[sub], best[bit][i] = sub;
            }
        }

        // find opt answer
        int cur = 0;
        for (int bit = 1; bit < (1<<k); bit++)
            if (dp[bit][rem]+mine[((1<<k)-1)-bit] > dp[cur][rem]+mine[((1<<k)-1)-cur])
                cur = bit;

        opt = dp[cur][rem]+mine[((1<<k)-1)-cur];

        // reconstruct useful team members
        while (cur > 0){
            extra.pb(who[best[cur][rem]]);
            cur -= best[cur][rem];
            rem--;
        }

        // add useless members
        sort(extra.begin(), extra.end());
        /*printf("mem now:");
        for (int j = 0; j < extra.size(); j++)
            printf(" %d", extra[j]);
        printf("\n");*/
        for (int i = n-1, j = (int)extra.size()-1; i >= 0 && rem; i--){
            while (j > 0 && extra[j] > i)
                j--;

            if ((j < 0 || i != extra[j]) && !block[i] && !must[i])
                extra.pb(i), rem--;
        }
    }

    bool operator<(const node &a) const{
        return (opt < a.opt);
    }

    void print(){
        printf("opt = %d\n", opt);

        printf("blocked:");
        for (int i = 0; i < n; i++)
            if (block[i])
                printf(" %d", i);
        printf("\n");

        printf("must:");
        for (int i = 0; i < n; i++)
            if (must[i])
                printf(" %d", i);
        printf("\n");

        printf("extra:");
        for (int i = 0; i < extra.size(); i++)
            printf(" %d", extra[i]);
        printf("\n");
    }
};

priority_queue<node> pq;

int main(){
    scanf("%d %d %d", &n, &k, &c);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
            scanf("%d", &par[i][j]);

    for (int i = 0; i < n; i++)
        for (int bit = 0; bit < (1<<k); bit++)
            for (int j = 0; j < k; j++)
                if (bit&(1<<j))
                    sum[i][bit] += par[i][j];

    int ans;
    bitset<len> block, must;
    pq.push(node(block, must));
    while (!pq.empty()){
        node u = pq.top();
        pq.pop();
        c--;

        //printf("c = %d, node u =\n", c);
        //u.print();

        if (c == 0){
            ans = u.opt;
            break;
        }

        block = u.block;
        must = u.must;
        for (int j = 0; j < u.extra.size(); j++){
            //printf("extra = %d\n", u.extra[j]);
            block[u.extra[j]] = 1;
            if (n-block.count() >= k){
                node v = node(block, must);
                //v.print();
                pq.push(v);
            }
            //printf("pushed\n");
            block[u.extra[j]] = 0;
            must[u.extra[j]] = 1;
        }
    }

    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

olympiads.cpp: In member function 'void node::print()':
olympiads.cpp:106:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < extra.size(); i++)
                         ~~^~~~~~~~~~~~~~
olympiads.cpp: In function 'int main()':
olympiads.cpp:144:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < u.extra.size(); j++){
                         ~~^~~~~~~~~~~~~~~~
olympiads.cpp:147:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (n-block.count() >= k){
                 ~~~~~~~~~~~~~~~~^~~~
olympiads.cpp:115:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &k, &c);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
olympiads.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &par[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 24 / 24
• Subtask 4: 32 / 32