제출 #916738

#제출 시각아이디문제언어결과실행 시간메모리
916738NintsiChkhaidzeGroup Photo (JOI21_ho_t3)C++17
44 / 100
5026 ms548 KiB
#include <bits/stdc++.h> #define ll long long #define s second #define f first #define pb push_back #define pii pair <int,int> #define left (h<<1),l,(l + r)/2 #define right ((h<<1)|1),(l + r)/2 + 1,r #define int ll using namespace std; const int N = 5e3 + 3,inf = 1e18; int a[N],dp[N],id[N],b[N]; signed main() { ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL); int n; cin>>n; for (int i = 1; i <= n; i++) cin >> a[i],dp[i] = inf,id[a[i]] = i; //neli for (int i = 1; i <= n; i++){ for (int k = 1; k <= i; k++){ int cost = 0; for (int j = 1; j <= n; j++) if (a[j] > i) b[j] = 1; else b[j] = 0; //marcxniv ramdenia i-ze meti for (int j = i; j >= i - k + 1; j--) for (int w = 1; w <= id[j]; w++) cost += b[w]; //anti inverse ebis raodenoba [i - k + 1, i] shualedshi for (int j = 1; j <= n; j++) b[j] = 0; for (int j = i; j >= i - k + 1; j--){ b[id[j]] = 1; for (int w = id[j] + 1; w <= n; w++) cost += b[w]; } dp[i] = min(dp[i],dp[i - k] + cost); } } cout<<dp[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...