提出 #44085353

---

ソースコード 拡げる

// Sachin Mahawar
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pair<ll, ll>> vpll;
typedef vector<vector<ll>> vvll;

#define ff(i, x, n) for (ll i = x; i < n; i++)
#define fb(i, n, x) for (ll i = n; i >= x; i--)
#define out(v, n)                        \
    ff(i, 0, n) { cout << v[i] << " "; } \
    cout << endl;
#define yes cout << "Yes\n"
#define no cout << "No\n"
#define fs first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
#define inf 1000000000000000005
const ll mod = 1000000007;
const ll mod2 = 998244353;
#define fast                          \
    std::ios::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define add(a, b, m) (((a % m) + (b % m) + m) % m)
#define sub(a, b, m) (((a % m) - (b % m) + m) % m)
#define mul(a, b, m) (((a % m) * (b % m) + m) % m)

// ---------------------------------Policy Based DataStructures-----------------------
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <class T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T>
using omulset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//  .find_by_order(x) : index of the x element in the set starting from 0
//  .order_of_key(x)  : number of elements strictly smaller than x in the set
// -----------------------------------------------------------------------------------

void brrrr()
{
    ll n,m;cin>>n>>m;
    vvll v(3,vll());
    for(ll i=0;i<n;i++){
        ll t,x;cin>>t>>x;
        v[t].push_back(x);
    }

    sort(all(v[0]),greater<ll>());
    sort(all(v[1]),greater<ll>());
    sort(all(v[2]),greater<ll>());

    for(ll i=1;i<(ll)v[2].size();i++){
        v[2][i]+=v[2][i-1];
    }
    for(ll i=1;i<(ll)v[1].size();i++){
        v[1][i]+=v[1][i-1];
    }
    for(ll i=1;i<(ll)v[0].size();i++){
        v[0][i]+=v[0][i-1];
    }

    ll res = 0;
    for(ll i=0;i<=min(m,(ll)v[0].size());i++){
        ll rem = m - i;

        ll j = (ll)v[1].size()-1;
        if(rem <= (ll)v[1].size()){
            j = rem-2;
        }

        ll k = max(0ll,rem-(ll)v[1].size()-1);
        k = min(k, max(0ll,(ll)v[2].size()-1));
        ll curr = 0; 

        // cout << i-1 << " " << j << " " << k << "######\n";

        while(j>=0 && k<(ll)v[2].size()){
            // cout << "take0: "<< i-1 << "\n";
            // cout << "take1: "<< j << " " << v[1][j] <<  "\n";
            // cout << "take2: "<< k << " " << v[2][k] <<  "\n";
            if(v[2][k] >= j+1){
                curr = v[1][j];
                break;
            }else{
                j--;
                k++;
            }
        }

        res = max(res,(i ? v[0][i-1] : 0) + curr);

    }

    cout<<res<<"\n";




}

int main()
{
    fast;
    ll t = 0;
    if (t)
    {
        cin >> t;
        for (ll i = 1; i <= t; i++)
        {
            brrrr();
        }
    }
    else
    {
        brrrr();
    }
    return 0;
}

提出情報

ジャッジ結果