Submission #867216

#	Time	Username	Problem	Language	Result	Execution time	Memory
867216		prohacker	Financial Report (JOI21_financial)	C++14	48 / 100	108 ms	1368 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const int N = 7005;
const int INF = INT_MAX;
const int mod = 1e9+7;

int n,rmq[N][15];
int a[N],dp[N];
int D,lg[N];
multiset<int> s;

void pre_calc() {
    for(int i = 1 ; i < D ; i++) {
        s.insert(a[i]);
    }
    for(int i = 1 ; i <= n-D+1 ; i++) {
        s.insert(a[i+D-1]);
        rmq[i][0] = *s.begin();
        s.erase(s.find(a[i]));
    }
    for(int j = 1 ; (1 << j) <= n ; j++) {
        for(int i = 1 ; i + (1 << j) - 1 <= n ; i++) {
            rmq[i][j] = max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
        }
    }
}

int get(int u, int v) {
    int k = lg[v-u+1];
    return max(rmq[u][k],rmq[v-(1<<k)+1][k]);
}

signed main()
{
    if (fopen("financial.inp", "r")) {
        freopen("financial.inp", "r", stdin);
        freopen("financial.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> D;
    for(int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for(int i = 1 ; i <= n ; i++) {
        lg[i] = __lg(i);
    }
    pre_calc();
    for(int i = 1 ; i <= n ; i++) {
        dp[i] = 1;
        for(int j = i-1 ; j > 0 ; j--) {
            if(i-j <= D) {
                if(a[i] > a[j]) {
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
            else {
                if(a[j] < a[i] && get(j+1,i-D) <= a[j]) {
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
    }
    cout << *max_element(dp+1,dp+n+1);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void pre_calc()':
Main.cpp:27:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |             rmq[i][j] = max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
      |                                                   ~^~
Main.cpp: In function 'int main()':
Main.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen("financial.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen("financial.out", "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