oj.uz

Submission #758535

# Submission time Handle Problem Language Result Execution time Memory
758535 2023-06-14T19:01:23 Z Ronin13 Olympiads (BOI19_olympiads) C++14
24 / 100
 211 ms 162788 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 200001;
map <vector <int>, bool > mp;
vector <vector <int> > vv[6000001];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, k, c;
    cin >> n >> k >> c;
    int a[n + 1][k + 1];
    int Ans = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; ++j)
            cin >> a[i][j];
        int mx = 0;
    }
    for(int j = 1; j <= k; j++){
        int mx = 0;
        for(int i = 1; i <= n; i++)
            mx = max(mx, a[i][j]);
        Ans += mx;
    }

    vv[Ans].pb({});
    while(c--){
        while(vv[Ans].empty() && Ans >= 0) Ans--;
        vector <int> o = vv[Ans].back();
        /*for(int to : o){
            cout << to << ' ';
        }
        cout << "\n";*/
        vv[Ans].pop_back();
        bool used[n + 1];
        fill(used, used +n + 1, false);
        for(auto to : o){
            used[to] = true;
        }
        vector <vector <int> > vec(n + 1);
        int mx[k + 1], mx1[k + 1];
        int mxi[k + 1];
        fill(mx, mx + k + 1, -1e9);
        fill(mx1, mx1 + k + 1, -1e9);
        fill(mxi, mxi + k + 1, -1e9);
        for(int j = 1; j <= k; j++){
            for(int i = 1; i <= n; i++){
                if(used[i]) continue;
                if(mx[j] < a[i][j]){
                    mxi[j] = i;
                    swap(mx[j], mx1[j]);
                    mx[j] = a[i][j];
                }
                else mx1[j] = max(mx1[j], a[i][j]);
            }
            vec[mxi[j]].pb(j);
        }
        int cnt = 0;
        vector <int> cur;
        for(int i = 1; i <= n; i++){
            if(vec[i].empty()) continue;
            cur.pb(i);
        }
        for(int j = 1; j <= n; j++){
            if(cur.size() == k) break;
            if(vec[j].empty() && !used[j]){
                cur.pb(j);
            }
        }
        for(int j : cur){
            int Nans = Ans;
            for(int to : vec[j]){
                if(mx1[to] == -1e9) {
                    Nans = -1e9;
                    break;
                }
                Nans += mx1[to] - mx[to];
            }
            vector <int> no = o;
            no.pb(j);
            if(no.size() > n - k){
                continue;
            }
            int ind = no.size() - 1;
            while(ind > 0){
                if(no[ind] < no[ind - 1])
                    swap(no[ind], no[ind - 1]),ind--;
                else break;
            }
            if(Nans >= 0 && !mp[no])
                vv[Nans].pb(no), mp[no] = true;
        }
    }
    cout << Ans;
    return 0;
}

Compilation message

olympiads.cpp: In function 'int main()':
olympiads.cpp:23:13: warning: unused variable 'mx' [-Wunused-variable]
   23 |         int mx = 0;
      |             ^~
olympiads.cpp:71:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |             if(cur.size() == k) break;
      |                ~~~~~~~~~~~^~~~
olympiads.cpp:87:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   87 |             if(no.size() > n - k){
      |                ~~~~~~~~~~^~~~~~~
olympiads.cpp:64:13: warning: unused variable 'cnt' [-Wunused-variable]
   64 |         int cnt = 0;
      |             ^~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 146144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 143200 KB Output is correct
2 Correct 92 ms 143572 KB Output is correct
3 Incorrect 85 ms 143780 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 162788 KB Output is correct
2 Correct 139 ms 151984 KB Output is correct
3 Correct 130 ms 146584 KB Output is correct
4 Correct 137 ms 151340 KB Output is correct
5 Correct 211 ms 160500 KB Output is correct
6 Correct 77 ms 142496 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 107 ms 146144 KB Output isn't correct
2 Halted 0 ms 0 KB -