Submission #1271584

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271584		KALARRY	Financial Report (JOI21_financial)	C++20	48 / 100	4094 ms	2052 KiB

Main

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const int INF  = 1e9;

int N,D,a[300005],dp[300005],max_reach[300005];
map<int,int> prv_emf;

int main()
{
    scanf("%d%d",&N,&D);
    for(int i = 1 ; i <= N ; i++)
    {
        scanf("%d",&a[i]);
        a[i]++;
    }
    for(int i = 1 ; i <= N ; i++)
    {
        int r = i;
        int l = i;
        max_reach[i] = i;
        while(r - l + 1 <= D && l > 1)
        {
            l--;
            max_reach[i] = l;
            if(a[l] <= a[i])
                r = l;
        }
    }
    a[0] = 0;
    int ans = 0;
    for(int i = 1 ; i <= N ; i++)
    {
        dp[i] = 1;
        for(int l = max_reach[i] ; l < i ; l++)
            if(a[l] < a[i])
                dp[i] = max(dp[i],dp[l] + 1);
        ans = max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%d%d",&N,&D);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

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