2018 WUSTACM 新生交流群:829055498

Problem 1349. -- TLE

1349: TLE

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 140  Accepted: 67
[Submit][Status][Web Board]

Description

WH在刷题时,设计出了如下代码:

#include<stdio.h>

int main()

{

    int i,j,cnt,k,N,K,a[5555];

    scanf("%d%d",&N,&K);

    int ans=0;

    for(i=1;i<=N;i++) scanf("%d",&a[i]);

    for( i=1;i<=N;i++)

      for(j=i+1;j<=N;j++)

       {

           cnt=0;

           for( k=i;k<=j;k++) cnt+=a[k];

           if(cnt%K==0) ans++;

       }

    printf("%d\n",ans);

}

上面的代码据说可能会TLE(不管你信不信,反正我是信了,不信你复制粘贴上去看看?)你的任务是重新设计一个更高效的程序帮助WH计算出ans的值

Input

第一行2个整数 N  K   N<= 5000  K>0

第二行N个数a[i]: 第i个数为a[i]    0<= a[i]<= 10000

Output

输出ans的值

Sample Input

5 1
1 2 3 4 5

Sample Output

10

[Submit][Status][Web Board]