Sum

Accepts: 322

Submissions: 940

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Problem Description

There is a number sequenceA1,A2....An,you can select a interval [l,r] or not,all the numbers Ai(l≤i≤r) will become f(Ai).f(x)=(1890x+143) mod 10007f(x)=(1890x+143)mod10007.After that,the sum of n numbers should be as much as possible.What is the maximum sum?

Input

There are multiple test cases. First line of each case contains a single integer n.(1≤n≤10^5) Next line contains (0≤Ai≤10^4) It's guaranteed that ∑n≤106.

Output

For each test case,output the answer in a line.

Sample Input

2

10000 9999

5

1 9999 1 9999 1

Sample Output

19999

22033

我们可以把所有的数都尝试的换一下，但是需要一个变量记录增长量，我们取增长量最大的加上初始的和就行

#include<stdio.h>

//#include<bits/stdc++.h>

#include<string.h>

#include<iostream>

#include<math.h>

#include<sstream>

#include<set>

#include<queue>

#include<vector>

#include<algorithm>

#include<limits.h>

#define inf 0x3fffffff

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

using namespace std;

int a[100010];

int main()

{

    int n;

    int i,j;

    __int64 sum,ans,Loli;

    int b;

    while(~scanf("%d",&n))

    {

        sum=0;Loli=0;ans=0;

        for(i=0;i<n;i++)

        {

            scanf("%d",&a[i]);

            sum+=a[i];

        }

     //   cout<<sum<<endl;

        for(i=0;i<n;i++)

        {

            if((a[i]*1890+143)%10007>a[i])

            {

                ans+=(a[i]*1890+143)%10007-a[i];

            }

            else if((a[i]*1890+143)%10007<=a[i])

            {

                ans-=a[i]-(a[i]*1890+143)%10007;

            }

            if(ans>Loli)

            {

                Loli=ans;

            }

           if(ans<0)

           {

               ans=0;

           }

          // cout<<ans<<endl;

        }

        if(Loli>0)

        {

            printf("%I64d\n",Loli+sum);

        }

        else

        {

            printf("%I64d\n",sum);

        }

    }

    return 0;

}

巴特西

BestCoder Round #64 1002

Sum

最新文章

热门文章