Submission #638903

#	Time	Username	Problem	Language	Result	Execution time	Memory
638903		Sofiatpc	Financial Report (JOI21_financial)	C++14	0 / 100	1 ms	212 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define sc second

const int MAXN = 405;
int N,D;
long long a[MAXN];
pair<int, long long> dp[MAXN][MAXN];
bool marc[MAXN];

pair<int, long long> fazdp(int i, int l)//qtd, mx
{
    if(dp[i][l].fi!=-1)return dp[i][l];

    if(l-i>D && l!=0)return dp[i][l]={0,0};

    if(i==1)return dp[i][l]={1,a[1]};


    int n = fazdp(i-1,l).fi;
    int s = fazdp(i-1,i).fi;
    if(fazdp(i-1,i).sc<a[i])s++;

    dp[i][l].fi=max(n,s);

    if(dp[i][l].fi==n)dp[i][l].sc=fazdp(i-1,l).sc;
    else dp[i][l].sc=max(fazdp(i-1,i).sc,a[i]);

    return dp[i][l];
}

int main()
{
    cin>>N>>D;
    for(int i = 1; i <= N; i++)cin>>a[i];

    for(int i = 1; i <= N; i++)
        for(int l = 0; l <= N; l++)dp[i][l].fi=-1;

    cout<<max(fazdp(N,0).fi+1,1)<<"\n";

}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35