Submission #908737

#TimeUsernameProblemLanguageResultExecution timeMemory
908737NeltExam (eJOI20_exam)C++17
0 / 100
1085 ms3416 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,avx2,fma,popcnt") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> /* DEFINES */ #define S second #define F first #define ll long long #define ull unsigned long long #define ld long double #define npos ULLONG_MAX #define INF LLONG_MAX #define vv(a) vector<a> #define ss(a) set<a> #define pp(a, b) pair<a, b> #define mm(a, b) map<a, b> #define qq(a) queue<a> #define pq(a) priority_queue<a> #define ump(a, b) unordered_map<a, b> #define ANDROID \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); #define allc(a) begin(a), end(a) #define all(a) a, a + sizeof(a) / sizeof(a[0]) #define elif else if #define endl "\n" #define pb push_back #define ins insert #define logi __lg #define sqrt sqrtl #define mpr make_pair using namespace std; using namespace __cxx11; using namespace __gnu_pbds; typedef char chr; typedef basic_string<chr> str; template <typename T, typename key = less<T>> using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void solve() { ll n; cin >> n; ll dp[n + 1]; ll a[n + 1], b[n + 1]; for (ll i = 1; i <= n; i++) cin >> a[i]; for (ll i = 1; i <= n; i++) cin >> b[i]; mm(ll, ll) mp; dp[0] = 0; for (ll i = 1; i <= n; i++) { dp[i] = dp[i - 1]; mp.clear(); ll mx = a[i]; for (ll j = i; j >= 1; j--) mp[b[j]]++, mx = max(mx, a[j]), dp[i] = max(dp[i], dp[j - 1] + (mp.count(mx) ? mp[mx] : 0)); } cout << dp[n] << endl; } /* */ int main() { ANDROID // precomp(); ll t = 1; // cin >> t; for (ll i = 1; i <= t; i++) // cout << "Case #" << i << ": ", solve(); cerr << "\nTime elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n"; }
#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...