oj.uz

Submission #787063

# Submission time Handle Problem Language Result Execution time Memory
787063 2023-07-18T17:58:21 Z Ahmed57 Zoltan (COCI16_zoltan) C++17
42 / 140
 1000 ms 64052 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;
    cout<<solve(n-1,n,0).first<<" "<<(solve(n-1,n,0).second*xd)%mod<<endl;
}

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 40 ms 31848 KB Output isn't correct
8 Incorrect 42 ms 31868 KB Output isn't correct
9 Incorrect 45 ms 31768 KB Output isn't correct
10 Incorrect 39 ms 31852 KB Output isn't correct
11 Runtime error 41 ms 64052 KB Execution killed with signal 11
12 Runtime error 40 ms 63992 KB Execution killed with signal 11
13 Runtime error 40 ms 63944 KB Execution killed with signal 11
14 Execution timed out 1076 ms 2128 KB Time limit exceeded
15 Execution timed out 1086 ms 2552 KB Time limit exceeded
16 Execution timed out 1071 ms 3036 KB Time limit exceeded
17 Runtime error 38 ms 63968 KB Execution killed with signal 11
18 Runtime error 46 ms 63964 KB Execution killed with signal 11
19 Runtime error 39 ms 63948 KB Execution killed with signal 11
20 Runtime error 41 ms 63948 KB Execution killed with signal 11