fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define forn(i,n) for(int i = 0; i < (n); i++)
  4. #define forsn(i,s,n) for(int i = (s); i < (n); i++)
  5. #define sq(x) ((x) * (x))
  6. #define all(v) ((v).begin, (v).end)
  7. #define pb push_back
  8. #define f first
  9. #define s second
  10. #define mp make_pair
  11. #define EPS 1e-10
  12.  
  13. using namespace std;
  14. typedef pair<int,int> par;
  15. typedef long long int tint;
  16.  
  17. int w[100100];
  18.  
  19. vector<int> ans;
  20.  
  21. /*
  22.  
  23. // Marsaglia
  24.  
  25. struct PRNG
  26. {
  27.     unsigned int Q[256];
  28.     unsigned int x,y,z,w,v,c; // Seed variables
  29.     int index;
  30.  
  31.     PRNG()
  32.     {
  33.         init();
  34.     }
  35.  
  36.     void init()
  37.     {
  38.         x = 123456789, y = 362436069, z = 521288629, w = 88675123, v = 886756453;
  39.         srand (time(NULL));
  40.         c = rand();
  41.         index = 0;
  42.     }
  43.  
  44.     void reset()
  45.     {
  46.         index = 0;
  47.         unsigned int aux[5];
  48.         forn(i,5)
  49.         {
  50.             aux[i] = (x^(x>>7)); x=y; y=z; z=w; w=v;
  51.             v=(v^(v<<6))^(aux[i]^(aux[i]<<13)); 
  52.             aux[i] = (y+y+1)*v;
  53.         }
  54.         x = aux[0], y = aux[1], z = aux[2], w = aux[3], v = aux[4];
  55.     }
  56.  
  57.     unsigned int xorshift()
  58.     {
  59.         if(index == RES) reset();
  60.  
  61.         index++;
  62.         unsigned int t;
  63.         t=(x^(x>>7)); x=y; y=z; z=w; w=v;
  64.         v=(v^(v<<6))^(t^(t<<13)); 
  65.         return (y+y+1)*v;
  66.     }
  67.  
  68.     unsigned int MWC256()
  69.     {
  70.         unsigned long long t,a=809430660LL;
  71.         static unsigned char i=255;
  72.         t=a*Q[++i]+c; c=(t>>32);
  73.         return(Q[i]=t);
  74.     }
  75.  
  76.     inline int next()
  77.     {
  78.         return xorshift();
  79.     }
  80.  
  81.     inline int next(int M) {
  82.         return xorshift() % M;
  83.     }
  84.     
  85.     inline int next(int a, int b) {
  86.         return a + (xorshift() % (b - a));
  87.     }
  88.     
  89.     inline double nextDouble() {
  90.         return (xorshift() + 0.5) * (1.0 / 4294967296.0);
  91.     }
  92. };
  93.  
  94. // Mersenne twister
  95.  
  96. struct RNG {
  97.     unsigned int MT[624];
  98.     int index;
  99.  
  100. 	RNG(int seed = 1) {
  101. 		init(seed);
  102. 	}
  103.     
  104.     void init(int seed = 1) {
  105.         MT[0] = seed;
  106.         forsn(i, 1, 624) MT[i] = (1812433253UL * (MT[i-1] ^ (MT[i-1] >> 30)) + i);
  107.         index = 0;
  108.     }
  109.     
  110.     void generate() {
  111.         const unsigned int MULT[] = {0, 2567483615UL};
  112.         forn(i, 227) {
  113.             unsigned int y = (MT[i] & 0x8000000UL) + (MT[i+1] & 0x7FFFFFFFUL);
  114.             MT[i] = MT[i+397] ^ (y >> 1);
  115.             MT[i] ^= MULT[y&1];
  116.         }
  117.         forsn(i, 227, 623) {
  118.             unsigned int y = (MT[i] & 0x8000000UL) + (MT[i+1] & 0x7FFFFFFFUL);
  119.             MT[i] = MT[i-227] ^ (y >> 1);
  120.             MT[i] ^= MULT[y&1];
  121.         }
  122.         unsigned int y = (MT[623] & 0x8000000UL) + (MT[0] & 0x7FFFFFFFUL);
  123.         MT[623] = MT[623-227] ^ (y >> 1);
  124.         MT[623] ^= MULT[y&1];
  125.     }
  126.     
  127.     unsigned int rand() {
  128.         if (index == 0) {
  129.             generate();
  130.         }
  131.         
  132.         unsigned int y = MT[index];
  133.         y ^= y >> 11;
  134.         y ^= y << 7  & 2636928640UL;
  135.         y ^= y << 15 & 4022730752UL;
  136.         y ^= y >> 18;
  137.         index = index == 623 ? 0 : index + 1;
  138.         return y;
  139.     }
  140.     
  141.     inline int next() {
  142.         return rand();
  143.     }
  144.     
  145.     inline int next(int x) {
  146.         return rand() % x;
  147.     }
  148.     
  149.     inline int next(int a, int b) {
  150.         return a + (rand() % (b - a));
  151.     }
  152.     
  153.     inline double nextDouble() {
  154.         return (rand() + 0.5) * (1.0 / 4294967296.0);
  155.     }
  156. };
  157.  
  158.  
  159. int main()
  160. {
  161.     freopen("out.txt", "w", stdout);
  162.  
  163.     //cout << RAND_MAX << endl;
  164.     RNG rng(1);
  165.     PRNG prng;
  166.  
  167.     //forn(i,10000) cout << rng.nextDouble() << " ";
  168.     //cout << endl;
  169.     forn(i,100000) cout << prng.nextDouble() << ", ";
  170.  
  171.     return 0;
  172. }
  173. */
  174.  
  175. void solve_dp(int n, tint m)
  176. {
  177.     bool dp[n+10][m+10]{ };
  178.     int prev[n+10][m+10];
  179.  
  180.     fill(*prev, *prev + (n+10)*(m+10), 0);
  181.  
  182.     forn(i,n+1) dp[i][0] = true;
  183.  
  184.     forsn(s,1,m+1)
  185.     {
  186.         forn(i,n)
  187.         {
  188.             dp[i+1][s] = dp[i][s];
  189.             if(s >= w[i])
  190.             {
  191.                 dp[i+1][s] |= dp[i][s-w[i]];
  192.             }
  193.             if(dp[i+1][s])
  194.             {
  195.                 if(!dp[i][s]) prev[i+1][s] = i+1;
  196.             }
  197.         }
  198.     }
  199.  
  200.  
  201.     for(int sum = m; sum >= 0; sum--)
  202.     {
  203.         if(dp[n][sum])
  204.         {
  205.             //cout << sum << endl;
  206.             int aux = sum;
  207.             int ind = n;
  208.             while(aux and ind)
  209.             {
  210.                 //cout << ind << " " << aux << " " << prev[ind][aux] << endl;
  211.                 if(prev[ind][aux] != 0)
  212.                 {
  213.                     ans.pb(ind-1);
  214.                     ind--;
  215.                     aux -= w[ind];
  216.                 }
  217.                 else ind--;
  218.             }
  219.             break;
  220.         }
  221.     }
  222. }
  223.  
  224.  
  225. int main()
  226. {
  227.     int n; tint m;
  228.  
  229. 	cin >> m >> n;
  230. 	forn(i,n) cin >> w[i];
  231.  
  232.  
  233. 	int lim = n;
  234.  
  235. 	if(n * m <= (tint)(1e7))
  236. 	{
  237. 	   solve_dp(n,m);
  238. 	}
  239. 	else
  240. 	{
  241. 	    tint acum = 0;
  242.  
  243. 	    for(int i = n-1; i >= 0; i--)
  244. 	    {
  245. 	        if(acum + w[i] > m)
  246. 	        {
  247. 	            lim = i;
  248. 	            break;
  249. 	        }
  250. 	        acum += w[i];
  251. 	    }
  252. 	    // something like 
  253. 	    solve_dp(lim, m - acum);
  254. 	}
  255.  
  256. 	sort(ans.begin(), ans.end());
  257. 	forsn(j,lim+1,n) ans.pb(j);
  258. 	int k = ans.size();
  259. 	cout << k << endl;
  260. 	forn(i,k) cout << ans[i] << " ";
  261. 	cout << endl;
  262. 	/*
  263. 	int ch = 0;
  264. 	forn(i,k) ch += w[ans[i]];
  265. 	cout << "CHECK" << endl;
  266. 	cout << ch << endl;
  267. 	*/
  268. 	return 0;
  269. }
Success #stdin #stdout 0s 4404KB
comments (?)
stdin
copy 
17 4
2 5 6 8
stdout
copy 
3
0 2 3
https://ideone.com/0NJUGZ
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!