Submission #1244616

#TimeUsernameProblemLanguageResultExecution timeMemory
1244616M_SH_OGroup Photo (JOI21_ho_t3)C++20
100 / 100
930 ms393396 KiB
/*#pragma GCC optimize("O3") #pragma GCC optimization("Ofast,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")*/ #include <bits/stdc++.h> /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>*/ #define ll long long #define ll1 long long #define ull unsigned long long #define dou long double #define str string #define vll vector<ll> #define vi vector<int> #define pll pair<ll, ll> #define vpll vector<pll> #define vbool vector<bool> #define vstr vector<str> #define vvll vector<vll> #define pb push_back #define pf push_front #define endl "\n" #define fr first #define se second // #define sortcmp(a) sort(a.begin(), a.end(), cmp) #define sort(a) sort(a.begin(), a.end()) #define reverse(a) reverse(a.begin(), a.end()) #define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define INF 1000000000000000007 #define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> using namespace std; //using namespace __gnu_pbds; mt19937 rng(time(0)); ll randll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); } int main(){ speed; srand(time(0)); ll n; cin >> n; vll a(n), b(n+7); for (int i =0 ; i < n; i ++) { cin >> a[i]; b[a[i]] = i; } vll dp(n+7, INF); dp[0] = 0; vvll p(n+7, vll(n+7, 0)), pr(n+7, vll(n+7, 0)); vbool us(n+7, 0); for (int i = 0; i < n; i ++) { us[a[i]] = 1; for (int j = 1; j <= n; j ++) { p[i][j] = p[i][j-1]+us[j]; } } us.clear(); us.resize(n+7, 0); for (int i = n-1; i >= 0; i --) { us[a[i]] = 1; for (int j = 1; j <= n; j ++) { pr[i][j] = pr[i][j-1]+us[j]; } } for (int i = 1; i <= n; i ++) { ll res = 0; for (int j = i; j >= 1; j --) { ll v = b[j]; res += p[v][n]-p[v][i]; res += pr[v][i]-pr[v][j]; dp[i] = min(dp[i], dp[j-1]+res); } } cout << dp[n] << endl; }
#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...