| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 771148 | VahanAbraham | Financial Report (JOI21_financial) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
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();
}
}