Submission #1032770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032770		vjudge1	Volontiranje (COCI21_volontiranje)	C++17	50 / 110	1034 ms	8016 KiB

Main

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

int main(){
    int n;
    cin >> n;

    int a[n];
    for (int i = 0; i < n; i ++)
        cin >> a[i];

    int lis = 0;
    int dp[n] = {}, par[n] = {};
    for (int i = n - 1; i >= 0; i --){
        dp[i] = 1;
        for (int j = i + 1; j < n; j ++)
            if (a[j] > a[i])
                dp[i] = max(dp[i], dp[j] + 1);
        lis = max(lis, dp[i]);
    }

    bool mark[n] = {};
    vector<vector<int>> output;
    for (int ii = 0; ii < n; ii ++){
        memset(dp, 0, sizeof dp);
        memset(par, 0, sizeof par);

        for (int i = n - 1; i >= 0; i --){
            if (mark[i]) continue;

            dp[i] = 1;
            par[i] = i;
            for (int j = i + 1; j < n; j ++){
                if (mark[j] or a[j] < a[i]) continue;
                if (dp[i] < dp[j] + 1 or (dp[i] == dp[j] + 1 and a[par[i]] < a[j])){
                    dp[i] = dp[j] + 1;
                    par[i] = j;
                }
            }
        }

        int mx = -1;
        for (int i = 0; i < n; i ++){
            if (dp[i] != lis) continue;
            if (mx == -1 or a[mx] < a[i])
                mx = i;
        }

        if (mx == -1) break;

        vector<int> cur;
        while (1){
            cur.push_back(mx);
            mark[mx] = 1;
            if (mx == par[mx]) break;
            mx = par[mx];
        }

        output.push_back(cur);
    }

    cout << output.size() << " " << lis << endl;
    for (auto vec : output){
        for (int x : vec)
            cout << x + 1 << " ";
        cout << endl;
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 0 / 60