No.3541 Progression (C++)
タグ : / 解いたユーザー数 27
作問者 :
Rho
/ テスター :
Problem Statement
You are given a sequence of positive integers $A = (A_1, A_2, \ldots, A_N)$ of length $N$.
Among the contiguous subarrays of $A$ that are arithmetic progressions, find the length of the longest one.
Input
$N$ $A_1\ A_2\ \ldots\ A_N$
- All input values are integers.
- $1 \leq N \leq 2000$
- $1 \leq A_i \leq 10^9$
Output
Output the answer on one line.
Trailing newlines and whitespace are ignored.
Score
Intended solution: $114$ bytes
Score Formula
If the code length of a submitted source code is $x$ and the code length of the intended solution of this problem is $y$, the score of that source code is $\max(500 - x + y, 100)$ points.The score for this problem is the maximum score among the source codes submitted to this problem.
Sample Program (C++)
An example solution in C++ is shown below. By submitting this code, you can obtain $194$ points.
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> A(N);
for(int i = 0; i < N; i++) {
cin >> A[i];
}
int ans = 1;
for(int i = 0; i < N - 1; i++) {
int d = A[i + 1] - A[i];
for(int j = i + 1; j < N; j++) {
if(A[j] - A[j - 1] != d) {
break;
}
if(ans < j - i + 1) {
ans = j - i + 1;
}
}
}
cout << ans << endl;
}
Sample
Sample 1
Input
5 3 1 4 7 5
Output
3
The contiguous subarray $(A_2, A_3, A_4)=(1, 4, 7)$ of $A$ is an arithmetic progression, and its length is $3$.
No contiguous subarray of $A$ that is an arithmetic progression has length greater than $3$, so output $3$.
Sample 2
Input
5 3 1 4 1 5
Output
2
Sample 3
Input
1 1000000000
Output
1
Sample 4
Input
10 10 9 8 7 6 5 4 3 2 1
Output
10
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。