# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
787063 | Ahmed57 | Zoltan (COCI16_zoltan) | C++17 | 1086 ms | 64052 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<iostream>
#include<queue>
using namespace std;
pair<long long,long long> dp[1001][1001][2];
long long n;int arr[1005];
long long mod = 1000000007;
pair<long long,long long> solve(int i,int la,int ss){
if(i==n&&ss){
return {0,1};
}
if(dp[i][la][ss]!=make_pair(-1ll,-1ll))return dp[i][la][ss];
pair<long long,long long> x = solve((ss?i+1:(i==0?1:i-1)),la,(ss|(i==0)));
if(arr[i]>arr[la]&&(!(ss&&i<la))){
pair<long long,long long> c1 = solve((ss?i+1:(i==0?1:i-1)),i,(ss|(i==0)));
c1.first++;
if(x.first<c1.first){
x = c1;
}else if(x.first==c1.first){
x.second+=c1.second;x.second%=mod;
}
}
return dp[i][la][ss] = x;
}
int main(){
cin>>n;
for(int i = 0;i<n;i++)cin>>arr[i];
for(int i = 0;i<=n;i++){
for(int j = 0;j<=n;j++){
dp[i][j][0] = {-1,-1};
dp[i][j][1] = {-1,-1};
}
}
arr[n] = 0;
long long xd = 1;
for(int i = 0;i<n-solve(n-1,n,0).first;i++)xd*=2;
cout<<solve(n-1,n,0).first<<" "<<(solve(n-1,n,0).second*xd)%mod<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |