DP/Easy/CodeForces

Run Settings
LanguageC++
Language Version
Run Command
#include <bits/stdc++.h> using namespace std; int main() { int n; cin>>n; vector<int> num(n); for(int i=0; i<n; i++){ cin>>num[i]; } vector<int> dp(n); vector<int> dp0(n); vector<int> dp1(n); if(n == 1){ if(num[0] == 0){ cout<<1; return 0; } } int c0 = 0; int c1 = 0; for(int i=0; i<n; i++){ if(num[i] == 0){ c0++; }else{ c1++; } dp0[i] = c0; dp1[i] = c1; } int check = 0; for(int i=0; i<n; i++){ if(num[i] == 1){ check++; } } if(check == n){ cout<<n-1; return 0; } int a = 0; int b = 0; int maxi = 0; for(int i=1; i<n; i++){ for(int j=0; j<i; j++){ int zero = dp0[i] - dp0[j]; int one = dp1[i] - dp1[j]; int next = dp0[i] - dp1[i]; int total = zero - one; total = total < 0 ? 0 : total; next = next < 0 ? 0 : next; // cout<<total<<" "; if(maxi < next){ maxi = next; a = 1; b = i+1; } if(maxi < total){ maxi = total; a = j+2; b = i+1; } } dp[i] = maxi; } // cout<<endl; // cout<<a<<" "<<b<<endl; int ans = 0; for(int i=0; i<n; i++){ if(i>=a-1 && i<=b-1){ if(num[i] == 0){ ans++; } }else{ if(num[i] == 1){ ans++; } } } cout<<ans; }
Editor Settings
Theme
Key bindings
Full width
Lines