제출 #1250284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1250284		herominhsteve	Financial Report (JOI21_financial)	C++17	19 / 100	260 ms	5920 KiB

Main

#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;
	}
}

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);
	}
};

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,-1);
		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[i])],dp[i][cur] + (a[i] > cur));
				}
			}
		}
		int res=0;
		for (int cur=0;cur<=m;cur++) maximize(res,dp[n][cur]);
		cout<<res;
		exit(0);
	}
};

namespace DPN2{
	void solve(){
		// ! dp[i]: Longest Increasing Subsequence collect and end at the element at index i
		vector<int> dp(n+1,1);
		dp[0]=0;
		for (int i=1;i<=n;i++){
			for (int j=i-1;j>=max(0,i-D);j--){
				if (a[i] > a[j]) maximize(dp[i],dp[j]+1);
			}
		}
		cout<< *max_element(allof(dp));
		exit(0);
	}
};

namespace SubtaskD1{
	void solve(){
		// ! dp[i]: Longest Increasing Subsequence collect and end at the element at index i
		vector<int> dp(n+1,1);
		dp[0]=0;
		for (int i=1;i<=n;i++){
			if (a[i] > a[i-1]) maximize(dp[i],dp[i-1]+1);
		}
		cout<< *max_element(allof(dp));
		exit(0);
	}	
};		

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;
		vector<multiset<int>> leaf;
		SegmentTree(int N=0){
			n=N;
			if (n>0){
				st.assign(4*n+1,0);
				leaf.resize(n+1);
			}
		} 
		void update(int node,int l,int r,int pos){
			if (l==r){
				st[node] = (leaf[pos].empty() ? 0 : *leaf[pos].rbegin());
				return; 
			}
			int mid = (l+r)>>1;
			if (pos<=mid) update(2*node,l,mid,pos);
			else update(2*node+1,mid+1,r,pos);
			st[node] = max(st[2*node],st[2*node+1]);
		}
		void update(int pos){
			update(1,1,n,pos);
		}
		void insert(int pos,int val){
			leaf[pos].insert(val);
			update(pos);
		}
		void erase(int pos,int val){
			multiset<int>::iterator it = leaf[pos].find(val);
			if (it != leaf[pos].end()) leaf[pos].erase(it);
			update(pos);
		}
		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(){
		SegmentTree st(n);
		vector<int> dp(n+1,0);
		for (int i=1;i<=n;i++){
			dp[i] = st.getMax(1,a[i]-1) + 1;
			st.insert(a[i],dp[i]);
			if (i>=D){
				st.erase(a[i-D],dp[i-D]);
			}
		}
		cout<<*max_element(allof(dp));
		exit(0);
	}
}

void sol(){
	if (n<=20) Bitmask2N::solve();
	if (n<=400) DPN3::solve();
	if (n<=7000) DPN2::solve();
	if (D==1) SubtaskD1::solve();
	if (D==n) NormalLIS::solve();
	Finale::solve();
}

int main(){
    setup();
    init();
    sol();
}

컴파일 시 표준 에러 (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);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35