Submission #1288818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288818		Faisal_Saqib	Financial Report (JOI21_financial)	C++20	48 / 100	100 ms	44356 KiB

Main

/* 
    VENI VIDI VICI
*/

// #pragma GCC optimize("Ofast","unroll-all-loops","fast-math","no-stack-protector","give-no-fuck")
#include <bits/stdc++.h>
// #include <iostream>
// #include <vector>
// #include <algorithm>
// #include <set>
// #include <map>

using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()

#define rep(i,x, n) for (int i = (x); i < (n); ++i)
#define repr(i,x, n) for (int i = (n) - 1; i >= (x); --i)
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());  
// #define sum accumulate

//using i128 = __int128;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
using sll = set<ll>;

template<class T>
istream& operator>>(istream& is, vector<T>& v) {
    for(auto &i:v) is>>i;
    return is;
}
template<class T1,class T2>
istream& operator>>(istream& is, pair<T1,T2>& p) {
    is>>p.fi>>p.se;
    return is;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    for(const auto &i:v) os<<i<<' ';
    return os;
}
template<class T1,class T2>
ostream& operator<<(ostream& os, const pair<T1,T2>& p) {
    os<<p.fi<<' '<<p.se; return os;
}
void pyn(bool x)
{
    cout<<(x?"YES":"NO")<<endl;
}
void pYN(bool x)
{
    cout<<(x?"Yes":"No")<<endl;
}
void pAB(bool x)
{
    cout<<(x?"Alice":"Bob")<<endl;
}
ll powmod(ll a,ll b,ll modulo)
{
  if(b==0){
    return 1;
  }
  ll temp=powmod(a,b/2,modulo);
  if(b%2==0){
    return (temp*temp)%modulo;
  }
  else{
    return (a*((temp*temp)%modulo))%modulo;
  }
}
bool Prime(ll n){
    for (ll i = 2; i*i <= n; i++)
        if (n % i == 0)
            return false;
    return (n>1);
}
void readIO() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
}

void solve();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    // readIO();

    int uwu=1;

    // cin>>uwu;

    for(int tc=1;tc<=uwu;tc++) {
        // cout<<"Case #"<<tc<<": ";
        solve();
    }
    return 0;
}
const int N=7000+2;
int a[N];
int dp[N][2];
// int dp[N];
bool can[N][N];
void solve()
{
    int n,d;
    cin>>n>>d;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        int l=i;
        for(int j=i-1;j>=0;j--)
        {
            if((l-j)<=d)
            {
                if(a[j]<=a[i])l=j;
                can[i][j]=1;
            }
        }
    }
    for(int i=1;i<=n;i++)dp[i][0]=1,dp[i][1]=1;;
    // for(int i=1;i<=n;i++)dp[i]=1;;
    for(int j=2;j<=n;j++)
    {
        for(int i=j-1;i>0;i--)
        {
            if(a[i]<a[j] and can[j][i])
                dp[j][0]=max((dp[i][0]+(a[i]<a[j]))*can[j][i],dp[j][0]);
            dp[j][1]=max((dp[i][1]),dp[j][1]);
            // cout<<"I: "<<i<<" J: "<<j<<' '<<can[j][i]<<' '<<(a[i]<a[j])<<endl;
            // cout<<dp[i]+(a[i]<a[j])*can[j][i]<<endl;
            // dp[j]=max(dp[j],(dp[i]+(a[i]<a[j]))*can[j][i]);
        }
        // cout<<"At "<<j<<' '<<dp[j][0]<<' '<<dp[j][1]<<endl;
        dp[j][1]=max(dp[j][1],dp[j][0]);
        // dp[j][0] = means j was maximum
        // dp[j][1] = means j was not maximum
    }
    // cout<<dp[n]<<endl;
    cout<<max(dp[n][0],dp[n][1])<<endl;
}

Compilation message (stderr)

Main.cpp: In function 'void readIO()':
Main.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:91:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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