Submission #758496

#	Time	Username	Problem	Language	Result	Execution time	Memory
758496		Ronin13	Olympiads (BOI19_olympiads)	C++14	0 / 100	45 ms	48380 KiB

olympiads

#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;

vector <vector <int> > vv[1000001];
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--;
        vector <int> o = vv[Ans].back();
        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);
        }
        for(int j = 1; j <= n; j++){
            int Nans = Ans;
            if(vec[j].empty()) continue;
            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(Nans >= 0)
                vv[Nans].pb(no);
        }
    }
    cout << Ans;
    return 0;
}

Compilation message (stderr)

olympiads.cpp: In function 'int main()':
olympiads.cpp:23:13: warning: unused variable 'mx' [-Wunused-variable]
   23 |         int mx = 0;
      |             ^~

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