oj.uz

Submission #392083

# Submission time Handle Problem Language Result Execution time Memory
392083 2021-04-20T12:35:13 Z nicolaalexandra Teams (CEOI11_tea) C++14
50 / 100
 2500 ms 48848 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23756 KB Output is correct
2 Correct 20 ms 23704 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct
4 Correct 15 ms 23816 KB Output is correct
5 Correct 15 ms 23748 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23764 KB Output is correct
2 Correct 15 ms 23724 KB Output is correct
3 Correct 15 ms 23756 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23684 KB Output is correct
2 Correct 15 ms 23804 KB Output is correct
3 Correct 16 ms 23756 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 23932 KB Output is correct
2 Correct 42 ms 23932 KB Output is correct
3 Correct 44 ms 23920 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 23924 KB Output is correct
2 Correct 37 ms 23924 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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