oj.uz

Submission #146543

# Submission time Handle Problem Language Result Execution time Memory
146543 2019-08-24T10:46:01 Z Alexa2001 Olympiads (BOI19_olympiads) C++17
13 / 100
 2000 ms 39784 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Nmax = 505, Kmax = 8;

map<ll, int> val;
int a[Kmax][Nmax];
vector<int> ord[Kmax];
int n, k, C;
bool used[Nmax];


struct myCmp
{
    bool operator () (ll x, ll y)
    {
        return (x == y ? x > y : val[x] < val[y]);
    }
};

priority_queue<ll, vector<ll>, myCmp> heap;

ll pwN[Kmax];


void next_state(vector<int> aux, int pos)
{
    int i, j;

//    cerr << pos << "#";
  //  for(auto it : aux) cerr << it << ' '; cerr << '\n';

    for(i=0; i<pos; ++i) 
    {
        assert(!used[ord[i][aux[i]]]);
        used[ord[i][aux[i]]] = 1;
    }

    ++aux[pos];
    while(aux[pos] < n && used[ord[pos][aux[pos]]]) ++aux[pos];
    
    if(aux[pos] == n) 
    {
        for(i=0; i<pos; ++i) used[ord[i][aux[i]]] = 0;
        return;
    }

    used[ord[pos][aux[pos]]] = 1;

    for(i=pos+1; i<k; ++i)
    {
        while(aux[i] < n && used[ord[i][aux[i]]]) ++aux[i];
        if(aux[i] == n) 
        {
            for(--i; i>=0; --i) used[ord[i][aux[i]]] = 0;
            return;
        }
        used[ord[i][aux[i]]] = 1;
    }

    ll state = 0;
    for(i=0; i<k; ++i)
        state += pwN[i] * aux[i];

    for(i=0; i<k; ++i) used[ord[i][aux[i]]] = 0;
    if(val[state]) return;

    for(i=0; i<k; ++i)
    {
        int best = 0;
        for(j=0; j<k; ++j)
            best = max(best, a[i][ord[j][aux[j]]]);
        val[state] += best;
    }

    heap.push(state);

 //   cerr << pos << '\n';
 //   for(i=0; i<k; ++i) cerr << ord[i][aux[i]] << ' '; cerr << '\n';
}

int main()
{
  //  freopen("olympiads.in", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> n >> k >> C;
    
    int i, j;

    for(i=1; i<=n; ++i)
        for(j=0; j<k; ++j)
            cin >> a[j][i];

    for(i=0; i<k; ++i)
    {
        for(j=1; j<=n; ++j) ord[i].push_back(j);
        
        auto cmp = [i] (int x, int y)
        {
            return (a[i][x] > a[i][y]);
        };

        sort(ord[i].begin(), ord[i].end(), cmp);
    }

    ll stt = 0;

    pwN[0] = 1;
    for(i=1; i<k; ++i) pwN[i] = pwN[i-1] * n;

    for(i=0; i<k; ++i)
    {
        for(j=0; j<n; ++j)
            if(!used[ord[i][j]]) break;
        stt += pwN[i] * j;

        used[ord[i][j]] = 1;
    }

    for(i=1; i<=n; ++i) used[i] = 0;

    heap.push(stt);
    for(i=0; i<k; ++i) val[stt] += a[i][ord[i][0]];

    map<ll, int> mp;

    while(C)
    {
        assert(heap.size());
        ll now = heap.top();
        heap.pop();

        ll cnow = now;

        vector<int> aux;
        for(i=0; i<k; ++i)
        {
            aux.push_back(now % n);
            now /= n;
        }

        vector<int> v;
        for(i=0; i<k; ++i) v.push_back(ord[i][aux[i]]);
        sort(v.begin(),v.end());

        ll vll = 0;
        for(i=0; i<k; ++i) vll += (v[i] - 1) * pwN[i];

        if(!mp[vll]) mp[vll] = 1, --C;
            
      //  for(auto it : v) cerr << it << ' '; cerr << '\n';

        if(C == 0)
        {
            cout << val[cnow] << '\n';
            return 0;
        }

    //    for(i=0; i<k; ++i)
      //      cerr << ord[i][aux[i]] << ' '; cerr << '\n';
        
        for(i=0; i<k; ++i)
        {
        //    for(j=1; j<=n; ++j) assert(used[j] == 0);
            next_state(aux, i);   
        }
    }    

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 888 KB Output is correct
2 Correct 9 ms 760 KB Output is correct
3 Correct 12 ms 888 KB Output is correct
4 Correct 6 ms 632 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2051 ms 39784 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1144 KB Output is correct
2 Correct 14 ms 1144 KB Output is correct
3 Correct 19 ms 1048 KB Output is correct
4 Correct 21 ms 1272 KB Output is correct
5 Correct 57 ms 2548 KB Output is correct
6 Execution timed out 2039 ms 34696 KB Time limit exceeded

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 888 KB Output is correct
2 Correct 9 ms 760 KB Output is correct
3 Correct 12 ms 888 KB Output is correct
4 Correct 6 ms 632 KB Output is correct
5 Execution timed out 2051 ms 39784 KB Time limit exceeded
6 Halted 0 ms 0 KB -