Submission #1267889

#TimeUsernameProblemLanguageResultExecution timeMemory
1267889Born_To_LaughTeam Contest (JOI22_team)C++17
0 / 100
1 ms328 KiB
// 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[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]); } if(ans == INF)cout << -1 << '\n'; else cout << ans << '\n'; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...