Blog

Miruna si Laura se joaca in fiecare zi cu N cuburi speciale. Pe fiecare dintre aceste cuburi sunt inscrise K numere naturale. Astazi cele doua fete au insirat toate cele N cuburi in linie, unul dupa altul. Ele vor sa aleaga un subsir de cuburi astfel incat oricare doua cuburi adiacente din subsir sa aiba cel putin un numar in comun. Ajutati-le sa gaseasca subsirul de lungime maxima!

Date de intrare

Fişierul de intrare cuburi5.in va contine pe prima linie doua numere naturale N si K, avand semnificatia din enunt. Fiecare din urmatoarele N linii va contine K valori naturale, reprezentand numerele inscrise pe cuburi.

Date de ieşire

În fişierul de ieşire cuburi5.out veti afisa indicii subsirului maximal ce respecta conditiile impuse. In cazul in care exista mai multe solutii, o veti afisa pe prima in ordine lexicografica.

Restricţii

• 1 ≤ N ≤ 50000
• 1 ≤ K ≤ 2000
• 1 ≤ N * K ≤ 1000000
• Valorile inscrise pe cuburi sunt din intervalul [1..100000]

Exemplu

using namespace std;
ifstream fin(“cuburi5.in”);
ofstream fout(“cuburi5.out”);
int n,k,i,j,p,maxx,mx,pf;
int dp[2][100001],sol[50001];
int main()
{
fin>>n>>k;
int a[n+1][k+1];

for(i=1;i<=n;i++)
    for(j=1;j<=k;j++)
        fin>>a[i][j];

for(i=n;i>=1;i--)
{
    mx=0;p=0;
    for(j=1;j<=k;j++)
      if(dp[0][a[i][j]]>mx)
    {
        mx=dp[0][a[i][j]];
         p=dp[1][a[i][j]];
    }
      else if(dp[0][a[i][j]]==mx&&dp[1][a[i][j]]<p)
         p=dp[1][a[i][j]];

    sol[i]=p;

    for(j=1;j<=k;j++)
    {
        dp[0][a[i][j]]=mx+1;
        dp[1][a[i][j]]=i;
    }

    if(mx+1>=maxx)
    {
        maxx=mx+1;
        pf=i;
    }
}

fout<<pf<<' ';

for(i=maxx-1;i>=1;i--)
{
    fout<<sol[pf]<<' ';
    pf=sol[pf];
}

return 0;

}