infoarena

 int k = 0;
    while(sol[poz_max] != 0)
           t[++k] = poz_max;
           poz_max = sol[poz_max];}

4
1 4
2 5
4 3
6 1

for ( i = 1; i <= n; i++ )
	{
		fin >> a[i].l >> a[i].g;
		b[i] = a[i];
	}
	do
	{
		gata = 1;
		for ( i = 1; i < n; i++ )
			if ( b[i].g < b[i+1].g )
			{
				aux = b[i];
				b[i] = b[i+1];
				b[i+1] = aux;
				gata = 0;
			}
	}
	while ( !gata );
	maxim[n] = 1;
	for ( i = n-1; i >= 1; i-- )
	{
		maxim[i] = 1;
		for ( j = i+1; j <= n; j++ )
			if ( b[i].l >= b[j].l && maxim[i] <= maxim[j] )
			{
				maxim[i] = maxim[j]+1;
				poz[i] = j;
			}
			if ( maxim[i] > max )
			{
				max = maxim[i];
				p = i;
			}
	}
	fout << max << ' ';
	i = p;
	while ( i != poz[n] )
	{
		s+=b[i].l;
		c[++k] = b[i];
		i = poz[i];
	}
	max = 0;
	min = 99999;
	for ( i = 1; i <= n; i++ )
	{
		if ( c[i].g > max )
		{
			max = c[i].g;
			max2 = c[i];
		}
		else
		if ( c[i].g < min && c[i].g != 0 )
		{
			min = c[i].g;
			min2 = c[i];
		}
	}
	fout << s << '\n';
	for ( i = 1; i <= n; i++ )
		if ( a[i].g == max2.g && a[i].l == max2.l )
			fout << i << '\n';
	for ( i = 2; i < k; i++ )
		for ( j = 1; j <= n; j++ )
			if ( a[j].l == c[i].l && a[j].g == c[i].g )
				fout << j << '\n';
			for ( i = 1; i <= n; i++ )
				if ( a[i].g == min2.g && a[i].l == min2.l )
					fout << i;
			fin.close();
			fout.close();
			return 0;
}

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct cub{
	int l,g,ind;
}v[4001];
bool comp(cub x,cub y){
	if(x.l==y.l)
		return (x.g<y.g);
	else 
		return (x.l<y.l);
}
vector < int > w;
int best[4001],poz[4001],nr[4001];
int main(){
	int n,i,p,j,mx=0;
	freopen("cuburi3.in","r",stdin);
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d",&v[i].l,&v[i].g);
		v[i].ind=i;
	}
	fclose(stdin);
	sort(v+1,v+n+1,comp);
	freopen("cuburi3.out","w",stdout);
	best[n]=v[n].l;
	poz[n]=-1;
	mx=v[n].l;
	p=n;
	nr[n]=1;
	for(i=n-1;i>=1;i--){
		poz[i]=-1;
		best[i]=v[i].l;
		for(j=i+1;j<=n;j++){
			if(v[i].g<v[j].g && best[i]<best[j]+v[i].l){
				best[i]=best[j]+v[i].l;
				poz[i]=j;
				nr[i]=nr[j]+1;
				if(best[i]>mx)
					mx=best[i],p=i;
			}
		}
	}
	printf("%d %d\n",nr[p],mx);
	i=p;
	while(i!=-1){
		w.push_back(v[i].ind);
		i=poz[i];
	}
	for(i=w.size()-1;i>=0;i--)
		printf("%d\n",w[i]);
	fclose(stdout);
	return 0;
}

20
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
1 20
2 19
3 18
4 17
5 16
6 15
7 14
8 13
9 12
19 11
20 10

11 74
20
10
9
8
7
6
5
4
3
2
1

10
1 10
2 9
3 8
4 7
5 6
6 5
7 4
8 3
9 2
10 1

1 10
10

void Sdmax()
{
    int Max,t,k;
    ind=0;
    l[N] = 1;
    h=0;
    for( k = N - 1 ; k ; --k )
    {
        Max = 0;
        for( i = k+1 ; i <= N ; ++i )
            if( v[i].l>=v[k].l && Max < l[i] )
                Max = l[i];
        l[k] = Max + 1;
    }
    Max = l[1];
    t = 1;
    for( k = 1 ; k <= N ; ++k )
        if( Max < l[k] )
    {
        Max = l[k];
        t =k;
    }
    kMax = Max;
    rez[++ind] = v[t].p;
    h += v[t].l;
    for( i = t + 1; i <= N ; ++i )
        if( v[i].l >= v[t].l && l[i] == Max - 1 ){
            rez[++ind] = v[i].p;
            h += v[i].l;
            --Max;
        }
}

for (i=1;i<=n;++i)
    {
        int Max=0;
        for (j=1;j<i;++j)
            if (a[j].g>=a[i].g)
                if (best[j]>Max) {
                    Max=best[j];
                    poz[i]=j;
                    L[i]=L[j]+1;}
        best[i]=Max+a[i].l;
        if (best[i]>=sum) sum=best[i],p=i,lmax=L[i];;
    }
    printf("%d %d\n",lmax,sum);