Submission #1271581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271581		KALARRY	Financial Report (JOI21_financial)	C++20	0 / 100	105 ms	16768 KiB

Main

//chockolateman

#include<bits/stdc++.h>

using namespace std;

const int INF  = 1e9;

int N,D,a[300005],dp[300005],prv_small[300005],prv_emf[300005],max_reach[300005];

int main()
{
    scanf("%d%d",&N,&D);
    for(int i = 1 ; i <= N ; i++)
    {
        scanf("%d",&a[i]);
        a[i]++;
    }
    a[0] = 0;
    multiset<int> active;
    active.insert(a[1]);
    for(int i = 2 ; i <= D ; i++)
    {
        prv_small[i] = 0;
        if(*active.begin() <= a[i])
        {
            auto it = active.upper_bound(a[i]);
            it--;
            prv_small[i] = *it;
        }
        active.insert(a[i]);
    }
    for(int i = D+1 ; i <= N ; i++)
    {
        prv_small[i] = 0;
        if(*active.begin() <= a[i])
        {
            auto it = active.upper_bound(a[i]);
            it--;
            prv_small[i] = *it;
        }
        active.insert(a[i]);
        int l = i - D;
        active.erase(active.find(a[l]));
    }
    prv_emf[0] = - INF;
    for(int i = 1 ; i <= N ; i++)
    {
        max_reach[i] = i;
        if(i - prv_emf[prv_small[i]] <= D)
            max_reach[i] = max_reach[prv_emf[prv_small[i]]];
        prv_emf[a[i]] = i;
    }
    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:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d%d",&N,&D);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

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