Submission #392083

#	Time	Username	Problem	Language	Result	Execution time	Memory
392083		nicolaalexandra	Teams (CEOI11_tea)	C++14	50 / 100	2578 ms	48848 KiB

tea

#include <bits/stdc++.h>
#define DIM 1000010
#define INF 2000000000
using namespace std;

pair <int,int> dp[DIM],v[DIM];
vector <int> sol[DIM];
int t[DIM];
int n,i,j,k;

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>v[i].first;
        v[i].second = i;
    }

    sort (v+1,v+n+1);
    reverse (v+1,v+n+1);

    /// dp[i] - nr maxim de secv in care pot imparti sirul si care e dimensiunea maxima minima

    for (i=1;i<=n;i++)
        dp[i] = make_pair(-INF,-INF);

    dp[0] = make_pair(0,0);
    for (i=1;i<=n;i++){
        int maxi = 0;
        for (int j=i;j<=n;j++){
            maxi = max (maxi,v[j].first);
            if (maxi > j-i+1)
                continue;
            if (dp[i-1].first + 1 > dp[j].first){
                dp[j].first = dp[i-1].first + 1;
                dp[j].second = max (dp[i-1].second,j-i+1);

                t[j] = i-1;
            } else {
                if (dp[i-1].first + 1 == dp[j].first && max (dp[i-1].second,j-i+1) < dp[j].second){
                    dp[j].second = max (dp[i-1].second,j-i+1);
                    t[j] = i-1;
                }
            }
        }
    }

    int x = n;
    while (x > 0){

        ++k;
        for (i=t[x]+1;i<=x;i++)
            sol[k].push_back(v[i].second);

        x = t[x];
    }

    cout<<k<<"\n";
    for (i=1;i<=k;i++){
        cout<<sol[i].size()<<" ";
        for (auto it : sol[i])
            cout<<it<<" ";
        cout<<"\n";
    }


    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10