Submission #771150

#	Time	Username	Problem	Language	Result	Execution time	Memory
771150		VahanAbraham	Financial Report (JOI21_financial)	C++14	Compilation error	0 ms	0 KiB

Main

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <cmath>
#include <vector>
#include <iomanip>
using namespace std;

#define ll long long
#define fr first
#define sc second
#define pb push_back
#define US freopen("revegetate.in", "r", stdin); freopen("revegetate.out", "w", stdout);
#define m_p make_pair
#define moo -1000000000000000;
#define poo 1000000000000000;

ll gcd(ll a, ll b)
{
    if (a == 0 || b == 0) {
        return  max(a, b);
    }
    if (a <= b) {
        return gcd(a, b % a);
    }
    else {
        return gcd(a % b, b);
    }
}

ll lcm(ll a, ll b) {
    return (a / gcd(a, b)) * b;
}

const int N = 300010;

//ll mx[N];
//ll a[N];
//ll b[N];
//ll ans[N];

vector<pair<ll int,ll int>> dp[405];
ll int mxx[405];
ll a[405];


void solve() {
    int n, d;
    cin >> n >> d;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
    }
    if (d == 1) {
        if (n == 1) {
            cout << 1 << endl;
            return;
        }
        ll pat = 1, l = n - 1, r = n;
        mx[n] = a[n];
        ans[n] = 1;
        for (int i = n - 1;i >= 1;i--) {
            ll kk = n + 1;
            r = n;
           // cout << i << " " << l << " " << r << endl;
            while (l <= r) {
                ll mid = (l + r) / 2;
                //cout << i << " " << mid << " " << mx[mid] << endl;
                if (mx[mid] > a[i]) {
                    kk = mid;
                    r = mid-1;
                }
                else {
                    l = mid+1;
                }
            }
            //cout << kk << " " << i << endl;
            if (kk != n + 1) {
                pat = max(ans[kk]+1, pat);
                ans[kk - 1] = ans[kk] + 1;
                mx[kk-1] = a[i];
                l = kk-1;
            }
            else {
                l = n;
                ans[l] = 1;
                mx[l] = a[i];
            }
        }
        cout << pat << endl;
        return;
    }
    if (n <= 400) {
        if (n == 1) {
            cout << 1 << endl;
            return;
        }
        dp[1].push_back({ a[1],1 });
        mxx[1] = 1;
        for (int i = 2;i <= n;i++) {
                for (int j = max(i - d,1);j < i;j++) {
                    for (int k = 0;k < dp[j].size();k++) {
                        if (dp[j][k].fr < a[i]) {
                            dp[i].push_back({ a[i],dp[j][k].sc + 1 });
                            mxx[i] = max(mxx[i], dp[i][dp[i].size() - 1].sc);
                        }
                        else {
                            dp[i].push_back({ dp[j][k].fr,dp[j][k].sc});
                            mxx[i] = max(mxx[i], dp[i][dp[i].size() - 1].sc);
                        }
                    }
                }
                dp[i].push_back({ a[i],1 });
                mxx[i] = max(mxx[i], dp[i][dp[i].size() - 1].sc);
        }
        cout << mxx[n] << endl;
    }
    /*for (int i = 1;i <= n;i++) {
        if (i > d) {
            for (int j = i - d;j < i;j++) {
                int l = 0;
                int r = dp[j].size() - 1, ind = -1;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (dp[j][mid].fr < a[i]) {
                        ind = mid;
                        l = mid + 1;
                    }
                    else {
                        r = mid - 1;
                    }
                }
                if (ind != -1) {
                    if (sum[ind] + 1 > mx) {
                        mx = sum[ind] + 1;
                    }
                }
                else {
                    for (int jj = 0;jj < dp[j].size();jj++) {
                        dp[i].push_back({ dp[j][jj].fr,dp[j][jj].sc });
                    }
                }
            }
            if (mx != -1) {
                dp[i].pb({ mx,a[i] });
            }
            sort(dp[i].begin(), dp[i].end());
        }
        else {

        }
    }*/
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    //US
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:70:9: error: 'mx' was not declared in this scope; did you mean 'mxx'?
   70 |         mx[n] = a[n];
      |         ^~
      |         mxx
Main.cpp:71:9: error: 'ans' was not declared in this scope; did you mean 'abs'?
   71 |         ans[n] = 1;
      |         ^~~
      |         abs
Main.cpp:112:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                     for (int k = 0;k < dp[j].size();k++) {
      |                                    ~~^~~~~~~~~~~~~~