Submission #66773443

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
#include <numeric>
using namespace std;
#define ll long long
#define vi vector<int>
#define vs vector<string>
#define vll vector<long long>
#define vii vector <<int>, <int>>
#define vllvector <<ll>, <ll>>
#define vb vector<bool>
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define rep(i, n) for (int i = 0; i < n; i++)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, health, magic;
    cin >> n >> health >> magic;
    vi enemy_health(n), enemy_magic(n);
    rep(i, n) {
        cin >> enemy_health[i] >> enemy_magic[i];
    }

    // number, health, magic
    queue<tuple<int, int, int>> q;
    set<tuple<int, int, int>> visited;
    // queue<tuple<int, int, int>> monster;

    q.emplace(0, health, magic);
    visited.emplace(0, health, magic);
    
    int max_kill = 0;
    while(!q.empty()) {
        tuple<int, int, int> t = q.front();
        q.pop();
        int i = get<0>(t);
        int hp = get<1>(t);
        int mp = get<2>(t);

        max_kill = max(max_kill, i);

        if(i == n) {
            continue;
        }

        if (mp >= enemy_magic[i]) {
            tuple<int, int, int> next = make_tuple(i +1, hp, mp - enemy_magic[i]);
            if(visited.count(next) == 0) {
                visited.insert(next);
                q.push(next);
            }
        }
        if(hp >= enemy_health[i]) {
            tuple<int, int, int> next = make_tuple(i + 1, hp - enemy_health[i], mp);
            if(visited.count(next) == 0) {
                visited.insert(next);
                q.push(next);
            }
        }
    }

    cout << max_kill << endl;

    return 0;
}

Submission Info

Judge Result