oj.uz

Submission #787065

# Submission time Handle Problem Language Result Execution time Memory
787065 2023-07-18T17:59:24 Z Ahmed57 Zoltan (COCI16_zoltan) C++17
70 / 140
 1000 ms 63988 KB 
#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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 39 ms 31792 KB Output is correct
8 Correct 42 ms 31828 KB Output is correct
9 Correct 43 ms 31828 KB Output is correct
10 Correct 38 ms 31828 KB Output is correct
11 Runtime error 52 ms 63964 KB Execution killed with signal 11
12 Runtime error 49 ms 63952 KB Execution killed with signal 11
13 Runtime error 48 ms 63936 KB Execution killed with signal 11
14 Execution timed out 1074 ms 816 KB Time limit exceeded
15 Execution timed out 1057 ms 900 KB Time limit exceeded
16 Execution timed out 1077 ms 972 KB Time limit exceeded
17 Runtime error 39 ms 63948 KB Execution killed with signal 11
18 Runtime error 40 ms 63988 KB Execution killed with signal 11
19 Runtime error 39 ms 63984 KB Execution killed with signal 11
20 Runtime error 40 ms 63892 KB Execution killed with signal 11