What is the problem with this code ?
I implemented dp here.
Can anyone tell any testcase where it fails ?
/*
Hey , this one is mine ..
make a new one for yourself
---->>AKASH KANDPAL
*/
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
using namespace std;
#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
const ll INF = ll(1e18);
const ld eps = 1e-9;
const ld pi = acos((ld) -1.0);
#define fi first
#define se second
#define pb push_back
#define po pop_back
#define mp make_pair
#define st string
#define vi vector<int>
int mod =1e6;
void add(int &x, int y) {
if ((x += y) >= mod) {
x -= mod;
}
}
int mult(int x, int y) {
return (long long) x * y % mod;
}
int power(int x, int pw) {
int res = 1;
for (; pw; pw >>= 1) {
if (pw & 1) {
res = mult(res, x);
}
x = mult(x, x);
}
return res;
}
const int MOD = (int)1e9 + 7;
const int N = 6066061 ;
/*vector<int> g[1000006];
bool vis[1000006],has[1000006];
stack<int> s;
void dfs(int z){
vis[z]=1;
s.push(z);
while(!s.empty()){
z=s.top();
s.pop();
for(int i=0;i<g[z].size();i++)
if(!vis[g[z][i]]){
vis[g[z][i]]=1;
s.push(g[z][i]);
}
}
return;
}
*/
int fa[1000005];
int find(int x){if(fa[x]!=x)fa[x]=find(fa[x]);return fa[x];}
int func()
{
}
int main(){
ios :: sync_with_stdio(0); cin.tie(0);
//cout << (fixed) << setprecision(10);
//bitset<2001> dp[2];
ll t,r,mini=1e10,maxi=-1e9;
ll z=1,n1,mid=0,d=0,u,num=0,n,q,i=0,x,y,l,e,f=0,j=0,m,p,pa,ans=0,k,sum=0,c1=0,c2=0,a[201201],b[201210],c[201201],sn=1,a1,b1;
string s1,s2;
ll maxi1=-1e9,maxi2=-1e9;
//bool vis[N];
//st s1[2]={"Bob","Alice"};
//vi v;
//map<int, int> mp;
//getline(cin,s);
//memset(dp , -1 , sizeof(dp));
//sort(s.begin(),s.end(),f);
//fill(dp+1,dp+4005,-1e9);
cin>>t;
while(t--){
cin>>n;
for(i=0;i<n;i++){cin>>a[i];sum+=a[i];}
z=0;
maxi1=-1e9;
if(n==2){
cout<<a[0]+a[1]-1<<endl;
}
else
{
for(i=0;i<n;i++)
{
if(a[i]>z){
z++;
b[i]=z;
}
else
{
z=1;
b[i]=z;
}
// cout<<b[i]<<" ";
}
z=0;maxi2=-1e9;
// cout<<endl;
for(i=n-1;i>=0;i--)
{
if(a[i]>z){
z++;
c[i]=z;
}
else
{
z=1;
c[i]=z;
}
// cout<<c[i]<<" ";
}
maxi=-1e9;
// cout<<endl;
for(i=0;i<n;i++){
if(b[i]>c[i]){
maxi=max(maxi,c[i]+1);//cout<<"hi"<<" ";
}
else{
maxi=max(maxi,min(b[i],c[i]));
}
}
if(maxi*2>n+1)maxi--;
// cout<<sum<<" "<<maxi<<" ";
sum-=(maxi*maxi);
cout<<sum<<endl;
sum=0;maxi=-1e9;z=0;
}}
return 0;
}
Please can anyone suggest some test cases where it fails ?
Thanks in advance .
Accepted Solution ::Code Link
