c++ - spoj CANDYSTN の制限時間超過

Question

  #include <iostream>
    using namespace std;
    int main()
    {
        long long int i,a,b,arr[10000]={0},dif,sum=0,tem=1,t;
        cin>>t;
        for(int m=0;m<t;m++)
        {
            cin>>a>>b;
            for(i=0;i<b;i++)
            {
                cin>>arr[i];
            }
            for(i=0;i<(b-1);i++)
            {
                dif=arr[i+1]-arr[i];
                sum=sum+dif;
                if(sum<=0 && tem>sum)
                {
                    tem=sum;
                }

            }
            if(a>(1-(tem)))
                cout<<1-tem<<"\n";
            else
                cout<<"-1"<<"\n";

        }
            return 0;
    }

https://ideone.com/vi7TVl これは私のコードへのリンクです。動的計画法を実装できません。

助けてください。時間を短縮するにはどうすればよいですか。

Answer 1

この問題は大量のデータを読み取る必要があるため、cin遅すぎます。代わりに使用できますscanf。

Answer 2

アレイを削除します。必要ありません。

2 つの変数と を使用presentしますprevious。present変数には、読み込まれた値が含まれます。変数previousには、以前に入力された値が含まれます。

2 つのループをなくすことができます。

  cin >> a >> b;
  int previous = 0;
  int present = 0;
  cin >> present;
  for (unsigned int i = 0; i < b - 1; ++i)
  {
    previous = present;
    cin >> present;
    dif = present - previous;
    sum += diff;
    if ( (sum < 0) && (tem > sum))
    {
      tem = sum;
    }
  }

ところで、変数名は 3 文字以上の長さにすることができます。