Submission #787065

#	Time	Username	Problem	Language	Result	Execution time	Memory
787065		Ahmed57	Zoltan (COCI16_zoltan)	C++17	70 / 140	1077 ms	63988 KiB

zoltan

#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;xd%=mod;
    }
    cout<<solve(n-1,n,0).first<<" "<<(solve(n-1,n,0).second*xd)%mod<<endl;
}

• Subtask 1: 70 / 140