又见采药

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k;
int nowF, nxtF;
vector<pair<int, int>> now, nxt, temp;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while (cin >> n >> k)
    {
        now.push_back(make_pair(0, 0));
        nxt.clear();
        temp.clear();
        for (int i = 1; i <= n; i++)
        {
            int ti, wi;
            cin >> ti >> wi;
            // 根据 now 计算 nxt
            for (auto x : now)
            {

                int nowT = x.first;
                int nowW = x.second;
                if (nowT + ti <= k)
                    nxt.push_back(make_pair(nowT + ti, nowW + wi));
            }
            // 合并 now、nxt 到 temp
            int pNow = 0;
            int pNxt = 0;
            int maxW = -1;
            while (pNow < now.size() && pNxt < nxt.size())
            {
                auto op1 = now[pNow];
                auto op2 = nxt[pNxt];
                if (op1.second < maxW)
                    pNow++;
                else if (op2.second < maxW)
                    pNxt++;
                else if (op1.first == op2.first)
                {
                    if (op1.second > op2.second)
                        temp.push_back(op1),
                            maxW = op1.second;
                    else
                        temp.push_back(op2),
                            maxW = op2.second;
                    pNow++, pNxt++;
                }
                else if (op1.first < op2.first)
                {
                    temp.push_back(op1);
                    maxW = op1.second;
                    pNow++;
                }
                else if (op1.first > op2.first)
                {
                    temp.push_back(op2);
                    maxW = op2.second;
                    pNxt++;
                }
            }
            while (pNow < now.size())
            {
                if (now[pNow].second > maxW)
                    temp.push_back(now[pNow]),
                        maxW = now[pNow].second;
                pNow++;
            }
            while (pNxt < nxt.size())
            {
                if (nxt[pNxt].second > maxW)
                    temp.push_back(nxt[pNxt]),
                        maxW = nxt[pNxt].second;
                pNxt++;
            }
            swap(now, temp);
            nxt.clear();
            temp.clear();
            if (i == n)
                cout << maxW << "\n";
        }
    }
    return 0;
}

/*
根据贪心原理，当费用相同时，只需保留价值最高的；
当价值一定时，只需保留费用最低的；
当有两件物品 i,j 且 i 的价值大于 j 的价值并且 i 的费用小于 j 的费用时，只需保留 i。
*/