Submission #1267884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267884		Born_To_Laugh	Team Contest (JOI22_team)	C++17	0 / 100	0 ms	328 KiB

team

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
using namespace std;
typedef long long ll;
[[maybe_unused]] const ll MOD = 998244353, INF = 1e9 + 7;
const int maxn = 4e3 + 10;
struct Fenwick_Tree
{
    int n;
    vector<int> bit;
    Fenwick_Tree(int len){
        n = len;
        bit.assign(n + 1, -INF);
    }
    void Point_Update(int pos, int val){
        for(; pos<=n; pos += pos & (-pos)){
            bit[pos] = max(bit[pos], val);
        }
    }
    int get(int pos){
        int ans = -INF;
        for(; pos>0; pos -= pos & -pos){
            ans = max(ans, bit[pos]);
        }
        return ans;
    }
};
Fenwick_Tree ft(maxn);
int n;
vector<array<int, 3>> item(maxn);
bool cmp(array<int, 3> a, array<int, 3> b){
    return a[0] < b[0];
}
void solve(){
    cin >> n;
    vector<int> temp;
    for(int i=1; i<=n; ++i){
        cin >> item[i][0] >> item[i][1] >> item[i][2];
        temp.push_back(item[i][1]);
    }
    sort(item.begin() + 1, item.begin() + 1 + n, cmp);
    sort(alle(temp));
    temp.erase(unique(alle(temp)), temp.end());
    auto get_pos = [&](int x){
        return upper_bound(alle(temp), x) - temp.begin();
    };
    int ans = -INF; 
    for(int i=1; i<=n; ++i){
        for(int j=1; j<i; ++j){
            if(item[j][1] <= item[i][1])continue;
            int num = ft.get(get_pos(item[j][1]) - 1);
            if(num < item[i][2] || num < item[j][2])continue;
            ans = max(ans, item[i][0] + item[j][1] + num);
            // cout << i << ' ' << j << ' ' << num << ' ' << ans << '\n';
        }
        ft.Point_Update(get_pos(item[i][1]), item[i][2]);
    }
    cout << ans << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27