제출 #1023869

#제출 시각아이디문제언어결과실행 시간메모리
1023869underwaterkillerwhaleGroup Photo (JOI21_ho_t3)C++17
100 / 100
358 ms165380 KiB
#include <bits/stdc++.h> #define se second #define fs first #define pb push_back #define ll long long #define ii pair<ll,ll> #define ld long double #define SZ(v) (int)v.size() #define ALL(v) v.begin(), v.end() #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) using namespace std; mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count()); ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); } const int N = 5e3 + 7; const ll Mod = 1e9 + 7; const int szBL = 916; const ll INF = 1e9; const int BASE = 137; int n, Q; int a[N]; int pos[N]; int cnt[N][N], cost[N][N]; int dp[N]; void solution () { cin >> n; rep (i, 1, n) { cin >> a[i]; pos[a[i]] = i; } rep (i, 1, n) { rep (j, 1, n) { cnt[i][j] = cnt[i - 1][j] + (a[i] >= j); } } rep (i, 1, n) rep (j, i, n) { cost[i][j] = cost[i][j - 1] + cnt[pos[j]][i] - cnt[pos[j]][j]; } memset(dp, 0x3f, sizeof dp); dp[0] = 0; rep (i, 1, n) { int curcost = 0; reb (j, i, 1) { curcost += cnt[pos[j]][i + 1]; dp[i]= min(dp[i], dp[j - 1] + curcost + cost[j][i]); } } cout << dp[n] <<"\n"; } #define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); int main () { // file("c"); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll num_Test = 1; // cin >> num_Test; while(num_Test--) solution(); } /* */
#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...