Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### mayank0802's blog

By mayank0802, history, 6 months ago, ,

• +15

 » 6 months ago, # |   +10 I'm under the impression that whenever you decrement some value it's optimal to take it all the way down to 1. Therefore, you can go for a dynamic programming approach to solve the problem, where dp[i][flag] = largest possible answer for the i-th prefix and flag indicates if the last element stayed at his value or if he was reduced to 1.
•  » » 6 months ago, # ^ |   0 kindly can you depict this thought in a solution or an algorithm.
 » 6 months ago, # | ← Rev. 2 →   0 code#include using namespace std; #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define ll long long #define pll pair #define pii pair #define pb push_back #define F first #define S second #define mod 1000000007 #define maxn 1000005 #define inf 1e18 #define boost ios::sync_with_stdio(false);cin.tie(0) #define fr freopen("source.txt","r",stdin),freopen("output.txt","w",stdout) #define SET(a,b) memset(a,b,sizeof(a)) ll a[maxn],dp[maxn][2]; ll n; ll go(ll i,ll j){ if(i==(n-1)) return 0; ll &ans=dp[i][j]; ans=0; if(i==0){ ans=max(ans,abs(a[i]-1)+go(i+1,1)); ans=max(ans,abs(a[i]-a[i+1])+go(i+1,0)); ans=max(ans,abs(1-a[i+1])+go(i+1,0)); } else if(j==0){ ans=max(ans,abs(a[i]-1)+go(i+1,1)); ans=max(ans,abs(a[i]-a[i+1])+go(i+1,0)); } else{ ans=max(ans,go(i+1,1)); ans=max(ans,abs(1-a[i+1])+go(i+1,0)); } return ans; } int main() { boost; ll i,j,x,t; cin>>t; while(t--){ cin>>n; for(i=0;i>a[i]; SET(dp,-1); cout<
•  » » 6 months ago, # ^ |   +1 Nobody got an AC on this problem, was there some problem with it's test cases? solution#include "bits/stdc++.h" using namespace std; #define int long long #define rep(i,a,n) for (int i = a; i <= n; ++i) const int N = 1e6 + 3; int dp[3][N]; int a[N]; inline void solve() { int n; cin >> n; rep(i,1,n) { dp[0][i] = dp[1][i] = dp[2][i] = 0; cin >> a[i]; } rep(i,2,n) { dp[0][i] = abs(a[i]-a[i-1]) + dp[2][i-1]; dp[1][i] = abs(a[i-1]-1) + max(dp[0][i-1], dp[2][i-1]); dp[2][i] = abs(a[i]-1) + dp[1][i-1]; } cout << max({dp[0][n], dp[1][n], dp[2][n]}) << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int t = 1; cin >> t; while(t--) solve(); return 0; } 
 » 4 weeks ago, # |   +8 Congratulation for creating the 69420th blog of codeforces