# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
284874 | arnold518 | Žarulje (COI15_zarulje) | C++14 | 18 ms | 16384 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==1 && r==N) return 1;
int &ret=dp[l][r];
if(ret!=-1) return ret;
if(l==0) return ret=solve(l, r+1);
if(r==N) return ret=solve(l-1, r);
if(A[l-1]<A[r+1]) return ret=solve(l, r+1);
if(A[l-1]>A[r+1]) 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, k));
}
}
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... |