Submission #1250643

#TimeUsernameProblemLanguageResultExecution timeMemory
1250643herominhsteveFinancial Report (JOI21_financial)C++17
100 / 100
630 ms23644 KiB
#include <bits/stdc++.h> #define el '\n' #define FNAME "IMPARR" #define allof(x) x.begin(),x.end() #define allof1(x) x.begin()+1,x.end() #define mset(x,n) memset(x,(n),sizeof(x)) using namespace std; const long long MOD = (long long) 1e9+7; template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;} template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;} void setup(){ ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); if (fopen(FNAME".inp","r")){ freopen(FNAME".inp","r",stdin); freopen(FNAME".out","w",stdout); } } int n,D; vector<int> a; void init(){ cin>>n>>D; vector<int> org(n); for (int &x:org) cin>>x; vector<int> compress(allof(org)); sort(allof(compress)); compress.resize(unique(allof(compress))-compress.begin()); a.resize(n+1,0); for (int i=1;i<=n;i++){ int t = lower_bound(allof(compress),org[i-1]) - compress.begin() + 1; a[i] = t; } } // ! ACed namespace Bitmask2N{ void solve(){ int MAXMASK = 1<<n; int res=0; for (int mask=0;mask<MAXMASK;mask++){ vector<int> indices; for (int i=0;i<n;i++){ if (mask & (1<<i)){ indices.push_back(i); } } vector<int> val; bool check=1; sort(allof(indices)); for (int i=1;i<(int)indices.size();i++){ if (abs(indices[i] - indices[i-1])>D){ check=0; break; } } if (!check) continue; for (int x:indices){ val.push_back(a[x+1]); } int score = 0, curmax = -1; for (int v : val) { if (v > curmax) { score++; curmax = v; } } maximize(res, score); } cout<<res; exit(0); } }; // ! ACed namespace DPN3{ void solve(){ int m = *max_element(allof(a)); // ! dp[pos][cur]: maximum impression score if ending at pos and max is cur int dp[n+1][m+1]; mset(dp,-0x3f3f3f); for (int i=1;i<=n;i++){ dp[i][a[i]]=1; } for (int i=1;i<=n;i++){ for (int cur=0;cur<=m;cur++){ if (dp[i][cur]==-1) continue; for (int nxt=i+1;nxt<=n and nxt-i <=D;nxt++){ maximize(dp[nxt][max(cur,a[nxt])],dp[i][cur] + (a[nxt] > cur)); } } } int res=0; for (int cur=0;cur<=m;cur++) maximize(res,dp[n][cur]); cout<<res; exit(0); } }; // ! ACed namespace NormalLIS{ void solve(){ vector<int> dp; vector<int> fordp(allof1(a)); for (int x:fordp){ vector<int>::iterator it = lower_bound(allof(dp),x); if (it == dp.end()) dp.push_back(x); else *it = x; } cout<<dp.size(); exit(0); } }; namespace Finale{ struct SegmentTree{ int n; vector<int> st; SegmentTree(int N=0){ n=N; if (n>0){ st.assign(4*n+1,0); } } void update(int node,int l,int r,int pos,int val){ if (l==r){ st[node] = val; return; } int mid = (l+r)>>1; if (pos<=mid) update(2*node,l,mid,pos,val); else update(2*node+1,mid+1,r,pos,val); st[node] = max(st[2*node],st[2*node+1]); } void update(int pos,int val){ update(1,1,n,pos,val); } int getMax(int node,int l,int r,int wanted_l,int wanted_r){ if (wanted_r<l or r<wanted_l) return 0; if (wanted_l<=l and r<=wanted_r) return st[node]; int mid = (l+r)>>1; return max(getMax(2*node,l,mid,wanted_l,wanted_r), getMax(2*node+1,mid+1,r,wanted_l,wanted_r)); } int getMax(int l,int r){ if (l>r) return 0; return getMax(1,1,n,l,r); } }; void solve(){ vector<int> perm(n,0); iota(allof(perm),1); sort(allof(perm),[](const int x,const int y){ if (a[x]==a[y]) return x>y; return a[x] < a[y]; }); set<int> processed; processed.insert(0); processed.insert(n+1); set<int> barrier; for (int i=1;i<=n-D;i++){ barrier.insert(i); } SegmentTree st(n); for (int x: perm){ set<int>::iterator it = processed.lower_bound(x); int prer = *it, prel = *(--it); if (prer-prel>D){ if (prer-x<=D) for (int i=x;i<=prer;i++) barrier.erase(i); if (x-prel<=D) for (int i=prel;i<=x;i++) barrier.erase(i); } processed.insert(x); it = barrier.lower_bound(x); int left = (it==barrier.begin() ? 1 : *(--it)); st.update(x,st.getMax(left,x-1)+1); } cout<<st.getMax(1,n); exit(0); } } void sol(){ if (n<=20) Bitmask2N::solve(); if (n<=400) DPN3::solve(); if (D==n) NormalLIS::solve(); Finale::solve(); } int main(){ setup(); init(); sol(); }

Compilation message (stderr)

Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
#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...