Submission #974336

#TimeUsernameProblemLanguageResultExecution timeMemory
974336berrGroup Photo (JOI21_ho_t3)C++17
100 / 100
656 ms392828 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N=5005; int ar[N][N], p[N][N],b[N], dp[N]; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n); for(auto &i: a) cin >> i; for(int i=1; i<=n; i++) dp[i]=1e9; for(int i=0; i<n; i++){ for(int l=0; l<i; l++){ ar[a[i]][a[l]]++; } for(int l=n-1; l>=0; l--){ ar[a[i]][l]+=ar[a[i]][l+1]; } } //her i l için bir prefix sum for(int i=0; i<=n; i++){ for(int l=0; l<=n; l++){ p[i][l]=ar[l][i]; if(l!=0) p[i][l]+=p[i][l-1]; } b[i]+=ar[i][i]; if(i!=0) b[i]+=b[i-1]; } for(int i=1; i<=n; i++){ int v=0; for(int l=i-1; l>=0; l--){ int v=0; v+=p[i+1][i]-p[i+1][l]; v+=p[l+1][i]-p[l+1][l]; v-=b[i]-b[l]; dp[i]=min(dp[i], dp[l]+v); } // cout<<"-----"<<dp[i]<<"\n"; } cout<<dp[n]; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:37:13: warning: unused variable 'v' [-Wunused-variable]
   37 |         int v=0;
      |             ^
#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...