# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
284887 | arnold518 | Ruka (COI15_ruka) | C++14 | 580 ms | 524288 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2000;
const int MOD = 1e9+7;
int N, A[MAXN+10], Q;
int dp[MAXN+10][MAXN+10];
int solve(int l, int r)
{
if(l>r) return 0;
if(l==0 && r==N+1) return 1;
if(dp[l][r]!=-1) return dp[l][r];
int &ret=dp[l][r];
if(l==0) return ret=solve(l, r+1);
if(r==N+1) return ret=solve(l-1, r);
if(A[l]<A[r]) return ret=solve(l, r+1);
if(A[l]>A[r]) return ret=solve(l-1, r);
return ret=(solve(l-1, r)+solve(l, r+1))%MOD;
}
int main()
{
scanf("%d%d", &N, &Q);
for(int i=1; i<=N; i++) scanf("%d", &A[i]);
memset(dp, -1, sizeof(dp));
while(Q--)
{
int k;
scanf("%d", &k);
printf("%d\n", solve(k-1, k+1));
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |