My accepted solution. I am using DP to precompute, each interval. ar[i][j]
gives the answer for interval i to j;
for(i=0;i<n;i++)
ar[i][i] = v[i]*n;
for(i=n-2;i>=0;i--)
for(j=i+1;j<n;j++)
ar[i][j] =
max(ar[i+1][j]+v[i]*(n-(j-i)),ar[i][j-1]+v[j]*(n-(j-i)));
output ar[0][n-1];
On Tue, Mar 8, 2011 at 10:49 PM, Logic King <crazy.logic.k...@gmail.com>wrote:
> I submitted it in g++4.3.2 it was AC...........but acc. to you it should
> have been error.......i think you are wrong somewhere !!
>
>
> On Tue, Mar 8, 2011 at 10:46 PM, abhijith reddy
> <abhijith200...@gmail.com>wrote:
>
>> <algorithm> isn't required for C++ 4.0.*. The same code will give Compile
>> Error in C++ 4.3 and above
>>
>>
>>
>> On Tue, Mar 8, 2011 at 10:42 PM, Logic King
>> <crazy.logic.k...@gmail.com>wrote:
>>
>>> Well tried,
>>> i have got the correct answer after working on it for almost 2 hours
>>> here is my code
>>>
>>> #include<iostream>
>>> using namespace std;int a[100][100];main(){int
>>> t,n,i,j;cin>>t;while(t--){cin>>n;for(i=0;i<n;i++){for(j=0;j<=i;j++)cin>>a[i][j];}for(i=n-2;i>=0;i--){for(j=0;j<=i;j++){a[i][j]+=max(a[i+1][j],a[i+1][j+1]);}}cout<<a[0][0]<<"\n";}}
>>>
>>>
>>> 246 bytes in c++.....i got it AC :)
>>> one amazing thing i found in my code, while reducing number of bytes,
>>> i.e.in my code max function is working even without using Algorithm
>>> header file........i dont know why it is working but it is working........if
>>> anyone know the reason for this then please share it
>>>
>>> Thank you,
>>> Logic King
>>>
>>> On Mon, Mar 7, 2011 at 8:25 PM, Wladimir Tavares
>>> <wladimir...@gmail.com>wrote:
>>>
>>>> This my code:
>>>> #include <stdio.h>
>>>> #define R(i,b) for(i=0;i<b;i++)
>>>> #define D(i,a) for(i=a;i>=0;i--)
>>>>
>>>> #define I(d) scanf("%d",&d);
>>>>
>>>> main(){int t,n,i,j,m[100][100];I(t)
>>>> while(t--){I(n)R(i,n)R(j,i+1)I(m[i][j]) D(i,n-2)R(j,i+1)m[i][j] +=
>>>> m[i+1][j]
>>>> > m[i+1][j+1]?m[i+1][j]:m[i+1][j+1];printf("%d\n",m[0][0]);}}
>>>>
>>>>
>>>> 297 bytes!
>>>>
>>>>
>>>>
>>>>
>>>> On Mon, Mar 7, 2011 at 11:45 AM, Wladimir Tavares <
>>>> wladimir...@gmail.com> wrote:
>>>>
>>>>> I create some macros like this:
>>>>>
>>>>> #define R(i,a,b) for(i=a;i<b;i++)
>>>>> #define D(i,a,b) for(i=a;i>=b;i--)
>>>>> #define I(d) scanf("%d",&d);
>>>>>
>>>>>
>>>>>
>>>>> But i don't get the accepted in this problem!
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> On Sun, Mar 6, 2011 at 1:55 PM, Logic King <crazy.logic.k...@gmail.com
>>>>> > wrote:
>>>>>
>>>>>> i solved the problem on spoj based on DP i am getting the solution
>>>>>> right but i am exceeding the following restriction
>>>>>> "Take care about your fingers, do not use more than *256* bytes of
>>>>>> code."
>>>>>>
>>>>>> http://www.spoj.pl/problems/SUMITR/
>>>>>>
>>>>>>
>>>>>> My code is--
>>>>>>
>>>>>> #include<stdio.h>
>>>>>> int arr[100][100];
>>>>>> int main()
>>>>>> {
>>>>>> int tc,n,max,i,j;
>>>>>> scanf("%d",&tc);
>>>>>> while(tc--)
>>>>>> {
>>>>>> scanf("%d",&n);
>>>>>> for(i=0;i<n;i++)
>>>>>> {
>>>>>> for(j=0;j<=i;j++)
>>>>>> scanf("%d",&arr[i][j]);
>>>>>> }
>>>>>> for(i=n-2;i>=0;i--)
>>>>>> {
>>>>>> for(j=0;j<=i;j++)
>>>>>> {
>>>>>>
>>>>>> max=(arr[i+1][j]>arr[i+1][j+1])?arr[i+1][j]:arr[i+1][j+1];
>>>>>> arr[i][j]=arr[i][j]+max;
>>>>>> }
>>>>>> }
>>>>>> printf("%d\n",arr[0][0]);
>>>>>> }
>>>>>> return 0;
>>>>>> }
>>>>>>
>>>>>>
>>>>>> how can i reduce my my code length so that it doesn't exceed 256
>>>>>> bytes....pl help !!
>>>>>>
>>>>>> --
>>>>>> You received this message because you are subscribed to the Google
>>>>>> Groups "Algorithm Geeks" group.
>>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>>> To unsubscribe from this group, send email to
>>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>>> For more options, visit this group at
>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>
>>>>>
>>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
