제출 #977315

#제출 시각아이디문제언어결과실행 시간메모리
977315AcanikolicFinancial Report (JOI21_financial)C++14
0 / 100
4035 ms6164 KiB
#include <bits/stdc++.h> #define int long long #define pb push_back #define F first #define S second using namespace std; const int N = 3e5 + 10; int a[N],dp[N],st[N * 4]; void modify(int node,int tl,int tr,int index,int val) { if(tl > index || tr < index) return; if(tl == tr) { st[node] = max(st[node],val); return; } int mid = (tl + tr) / 2; modify(node * 2,tl,mid,index,val); modify(node * 2 + 1,mid + 1,tr,index,val); st[node] = max(st[node * 2],st[node * 2 + 1]); } int get(int node,int tl,int tr,int l,int r) { if(l > r) return 0; if(tl > r || tr < l) return 0; if(tl >= l && tr <= r) return st[node]; int mid = (tl + tr) / 2; return max(get(node * 2,tl,mid,l,r),get(node * 2 + 1,mid + 1,tr,l,r)); } bool cmp(pair<int,int>A,pair<int,int>B) { if(A.F == B.F) return A.S < B.S; return A.F < B.F; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); /*int n,d; cin >> n >> d; for(int i = 1; i <= n; i++) { cin >> a[i]; dp[i] = 1; } vector<pair<int,int>>vec; for(int i = 1; i <= n; i++) vec.pb({a[i],i}); sort(vec.begin(),vec.end(),cmp); vector<pair<int,int>>updates; // update pos dpval for(int i = 0; i < n; i++) { if(i > 0 && vec[i].F != vec[i - 1].F) { for(auto X : updates) modify(1,1,n,X.F,X.S); updates.clear(); } int j = max(1ll,vec[i].S - d); updates.pb({vec[i].S,get(1,1,n,j,vec[i].S - 1) + 1}); } for(auto X : updates) modify(1,1,n,X.F,X.S); cout << get(1,1,n,1,n);*/ int n,d; cin >> n >> d; for(int i = 1; i <= n; i++) { cin >> a[i]; dp[i] = 1; } for(int i = 1; i <= n; i++) { for(int j = i - 1; j >= 1; j--) { if(i - j > d) break; if(a[i] > a[j]) dp[i] = max(dp[i],dp[j] + 1); } } int res = 0; for(int i = 1; i <= n; i++) res = max(res,dp[i]); cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...