1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// O(n*n)
#include <iostream>
using namespace std;
long n;  //  1 - 100 000  ile potworow
long z;   // 1 - 100 000  zycie poczatkowe
long d, a;  //koszt i zysk  1-100 000
long dd[100002];  //koszty
long zz[100002];  //zyski
bool juz[100002]; 
long odp[100002];
long long dzsum;
long minz, iminz;

int main() 
{
    ios_base::sync_with_stdio(0);
    cin>>n; cin>>z;
    dzsum=z;  minz=200000;
    for(long i=1; i<=n; i++)
    {
       cin>>dd[i]; cin>>zz[i]; 
       dzsum=dzsum+zz[i]-dd[i];
       if(zz[i]<minz) {minz=zz[i]; iminz=i;}
       juz[i]=false;
    }
    if(dzsum-minz<0) cout<<"NIE"<<endl; 
    
    else
    {
        juz[iminz]=true; odp[n]=iminz;      
        
        bool jest;                             
        for(long i=1; i<=n-1; i++)
        {
            //znajdz ix z max zyskiem bez przekroczenia z  =>jest =>ix
            long ix;    long maxzysk=-200000;
            jest=false;
            for(long j=1; j<=n; j++)
            {
                if(!juz[j] and (dd[j]<=z) and (zz[j]-dd[j] > maxzysk))
                {
                    maxzysk= zz[j]-dd[j]; 
                    ix=j; jest=true;
                }                
            }                        
            
            if(!jest)  { cout<<"NIE"<<endl; break; }
            else 
            {
                juz[ix]=true;
                odp[i]=ix;
                z= z - dd[ix] + zz[ix];                
            }        
        }
        
        if(jest)
        {
            cout<<"TAK"<<endl;
            for(long i=1; i<=n; i++) cout<<odp[i]<<" ";  cout<<endl;
        }
    }  
    
    
    return 0; 
}