Submission #372025

---

Source Code Expand

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <cassert>
#include <cstdio>
#include <bitset>

using namespace std;
typedef long long ll;


struct Trie {
    typedef Trie* TP;
    TP ch[10];
    ll u, ma;
    Trie() {
        fill_n(ch, 10, nullptr);
        u = ma = 0;
    }
    ll add(string s, int i, ll d) {
        if (i == (int)s.size()) {
            u += d;
            return ma+u;
        }
        int c = s[i] - '0';
        if (ch[c] == nullptr) {
            ch[c] = new Trie();
        }
        ma = max(ma, ch[c]->add(s, i+1, d));
        return ma+u;
    }
    ll get() {
        return ma+u;
    }
};

Trie tr;



int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        string s = to_string(a);
        reverse(s.begin(), s.end());
        tr.add(s, 0, b);
        cout << tr.get() << endl;
    }
    return 0;
}

Submission Info

Judge Result