Advertisement
Dang_Quan_10_Tin

BOX

Jun 25th, 2022
590
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. #define task "BOX"
  5. #define pll pair<ll, ll>
  6. #define pii pair<int, int>
  7. #define fi first
  8. #define se second
  9. using namespace std;
  10. const int mod = 998244353;
  11. const int N = 1e5+5;
  12. const int M = 5e3+5;
  13. const ll base = 257;
  14. const ll base1 = 311;
  15. int n, m, ans, dp[M], k, lst[N];
  16. bool trave[M*14][M];
  17. vector<pii> adj[N];
  18. struct box
  19. {
  20.     int c, w, id;
  21.     bool operator < (const box& b)
  22.     {
  23.         return c+w < b.c+b.w;
  24.     }
  25. }b[N];
  26. void sol(int itest)
  27. {
  28.     cin >> n;
  29.     for(int i = 1; i <= n; i ++)
  30.     {
  31.         int c, w;
  32.         cin >> c >> w;
  33.         adj[w].pb({c, i});
  34.     }
  35.     for(int i = 1; i <= 5000; i ++)
  36.     {
  37.         sort(adj[i].begin(), adj[i].end());
  38.         k = 5000/i+1;
  39.         while(!adj[i].empty() && k > 0)
  40.         {
  41.             --k;
  42.             ++m;
  43.             b[m].c = adj[i].back().fi;
  44.             b[m].id = adj[i].back().se;
  45.             adj[i].pop_back();
  46.             b[m].w = i;
  47.         }
  48.     }
  49.     sort(b+1, b+1+m);
  50.     fill_n(dp, M, -1);
  51.     fill_n(lst, m+1, -1);
  52.     dp[0] = 0;
  53.     k = 0;
  54.     for(int i = 1; i <= m; i ++)
  55.     {
  56.         for(int j = b[i].c; j >= 0; j --)
  57.         {
  58.             if(dp[j] == -1)continue;
  59.             int nxt = min(5001, j+b[i].w);
  60.             if(dp[nxt] < dp[j]+1)
  61.             {
  62.                 if(nxt == 5001)lst[i] = j;
  63.                 else trave[i][nxt] = 1;
  64.                 dp[nxt] = dp[j]+1;
  65.                 if(ans < dp[nxt])
  66.                 {
  67.                     ans = dp[nxt];
  68.                     k = nxt;
  69.                 }
  70.             }
  71.         }
  72.     }
  73.     cout << ans << '\n';
  74.     for(int i = m; i > 0; i --)
  75.     {
  76.         if(trave[i][k] && k <= 5000)
  77.         {
  78.             k -= b[i].w;
  79.             cout << b[i].id <<(k == 0 ? "\n" : " ");
  80.         }
  81.         else if(lst[i] != -1 && k == 5001)
  82.         {
  83.             k  = lst[i];
  84.             cout << b[i].id<<(k == 0 ? "\n" : " ");;
  85.         }
  86.     }
  87. }
  88. int main()
  89. {
  90.     if(fopen(task".inp", "r")){
  91.        freopen(task".inp", "r", stdin);
  92.        freopen(task".out", "w", stdout);
  93.     }
  94.     ios_base::sync_with_stdio(0);
  95.     cin.tie(0);
  96.     cout.tie(0);
  97.     int ntest;
  98.     ntest = 1;
  99.     //cin >> ntest;
  100.     for(int i = 1; i <= ntest; i ++)
  101.         sol(i);
  102. }
  103.  
  104.  
Advertisement
RAW Paste Data Copied
Advertisement