My array size is 100000.. try to increase yours..nymo wrote:Hi, I 've used an INT array of size 50000 and getting WA. Can someone provide some IOs? [I 've tried IOs posted on other threads]... THANKS. and THERE IS ONLY ONE TEST CASE, RIGHT?
I knew that url , I 've coded myself from the scratch and trying to figure out my fault... 
Thanks but some test cases would be really handy. thanks again.
Thanks.could you give me some idea about 481 ? THX!!mf wrote:TLE -- because your program isn't fast enough. Generate an input with 100000 random numbers, and you'll see why.
You have to find a better algorithm, or use some clever data structure to speed up yours.
Code: Select all
#include<iostream>
using namespace std;
int d[100000],t[100000],l[100000];//l link-d data-t time
void out(int i){
if(l[i]!=i)
out(l[i]);
cout <<d[i]<<endl;
}
int main( int argc, char * argv[] )
{
int i=0,j,a=0,b=0;
while(cin >>d[i]){
t[i]=1;l[i]=i;
if(d[i]>d[b]){
l[i]=b;
t[i]=(a++);
b=i;
}
else{
for(j=i-1;j>=0;j--)
if(d[j]<d[i]&&t[j]+1>t[i]){
t[i]=t[j]+1;
l[i]=j;
}
if(t[i]>=a){
a=t[i];
b=i;
}
}
i++;
}
cout <<a<<endl<<'-'<<endl;
out(b);
return 0;
}
Code: Select all
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
long long n;
vector <long long> num, v;
vector <vector <long long> > seq;
while (cin>>n){
num.push_back (n);
v.push_back (1);
seq.push_back (vector <long long> (1, n));
long long pos=num.size()-1, max=0;
for (int j=0; j<num.size()-1; j++){
if (num[j]<num[num.size()-1]) if (v[j]>=max){max=v[j]; pos=j;}
}
v[v.size()-1]=max+1;
seq[v.size()-1]=seq[pos];
if (pos!=num.size()-1)seq[v.size()-1].push_back (n);
}
if (num.size()==0) {cout<<0<<endl<<"-"<<endl;return 0;}
long long pos=0, max=0;
for (int i=0; i<v.size(); i++) if (v[i]>=max){max=v[i]; pos=i;}
cout<<max<<endl<<"-"<<endl;
for (int i=0; i<seq[pos].size(); i++) cout<<seq[pos][i]<<endl;
return 0;
}
Code: Select all
vector <vector <long long> > seq;Code: Select all
#include <iostream>
using namespace std;
int main ()
{
int n =0;
int MaxLength =1;
int k=0;
int Arr[50000];
int Length[50000];
int Seq[50000];
while (cin >>Arr[n])
{
n++;
}
for (int i = 0; i < n; i++)
{
Length[i]=1;
for (int j = 0; j < i; j++)
{
if(Arr[j]<Arr[i] && 1+Length[j] >Length[i])
Length[i] = Length[j]+1;
}
MaxLength = max(MaxLength,Length[i]);
}
for (int i = 0; i < n; i++)
{
if (MaxLength ==Length[i])
{
for (int j = 0; j < i; j++)
{
if (Arr[j] <Arr[i])
{
Seq[k] = Arr[j];
k++;
}
}
Seq[k] = Arr[i];
k++;
break;
}
}
cout <<MaxLength<<endl<<"-"<<endl;
for (int i = 0; i < k; i++)
{
cout <<Seq[i]<<endl;
}
return 0;
}