Cod sursa(job #2055186)

Utilizator GrandmasterSoucup Bogdan Grandmaster Data 2 noiembrie 2017 22:17:17
Problema Subsir 2 Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <fstream>
#include <math.h>
#include <vector>
#include <set>
#include <algorithm>
#include <cstring>
//#include <unordered_map>
#include <iomanip>
#include <time.h>
#include <stdio.h>
#include <bitset>
#include <map>
#include <ctime>
#include <stdlib.h>
#define MAX 500000000000
//#include <iostream>
//#include <windows.h>
#include <deque>
//#include "PEZai.h"
//#include <Tlhelp32.h>
using namespace std;
ifstream cin("subsir2.in");
ofstream cout("subsir2.out");
//ifstream cin("quadratum.in");
//ofstream cout("quadratum.out");
int n, dp[5004][3], x[5004], sols, mex = 0;
void rec(int r)
{
    if(dp[r][0] == 1)
        return;
    rec(dp[r][2]);
    cout << dp[r][2] + 1 << " ";
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x[i];
        dp[i][0] = 1;
        dp[i][1] = 1<<22;
        dp[i][2] = 1<<20;
    }
    for(int i = 0; i < n; i++)
    {
        for(int j = i - 1; j >= 0; j--)
        {
            if(x[i] >= x[j])
            {
                if(dp[i][0] == dp[j][0] + 1)
                {
                    if(dp[i][1] > x[j])
                    {
                        dp[i][1] = x[j];
                        dp[i][2] = j;
                    }
                }
                else if(dp[i][0] < dp[j][0] + 1)
                {
                    dp[i][0] = dp[j][0] + 1;
                    dp[i][1] = x[j];
                    dp[i][2] = j;
                    mex = max(mex, dp[i][0]);
                }
            }
        }
    }
    cout << mex << "\n";
    int val = 1<<20, ind = 0;
    for(int i = 0; i < n; i++)
    {
        if(dp[i][0] == mex)
        {
            if(x[i] < val)
            {
                val = x[i];
                sols = dp[i][2];
                ind = i;
            }
        }
    }
    rec(ind);
    cout << ind + 1;
}