제출 #1141266

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141266		SmuggingSpun	Financial Report (JOI21_financial)	C++20	65 / 100	2204 ms	116432 KiB

Main

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
const int INF = 1e9;
template<class T>bool maximize(T& a, T b){
	if(a < b){
		a = b;
		return true;
	}
	return false;
}
int n, d;
namespace sub1{
	void solve(){
		vector<int>a(n);
		for(int& x : a){
			cin >> x;
		}
		int ans = 0;
		for(int mask = (1 << n) - 1; mask > 0; mask--){
			vector<int>index;
			for(int i = 0; i < n; i++){
				if(1 << i & mask){
					if(!index.empty() && i - index.back() > d){
						index.clear();
						break;
					}
					index.emplace_back(i);
				}
			}
			if(!index.empty() && index.back() == n - 1){
				int cnt = 0, cur_max = -1;
				for(int& x : index){
					if(maximize(cur_max, a[x])){
						cnt++;
					}
				}
				maximize(ans, cnt);
			}
		}
		cout << ans;
	}
}
namespace sub5{
	const int LIM = 1e9 + 5;
	void solve(){
		map<int, int>bit;
		auto update = [&] (int p, int x){
			for(p++; p < LIM; p += p & -p){
				maximize(bit[p], x);
			}
		};
		auto get = [&] (int p){
			int ans = 0;
			for(; p > 0; p -= p & -p){
				auto it = bit.find(p);
				if(it != bit.end()){
					maximize(ans, it->second);
				}
			}	
			return ans;
		};
		for(int i = 0; true; i++){
			int x;
			cin >> x;
			int LIS = get(x) + 1;
			update(x, LIS);
			if(i + 1 == n){
				cout << get(LIM - 1);
				break;
			}
		}
	}
}
namespace sub4{
	void solve(){
		vector<int>a(n);
		for(int& x : a){
			cin >> x;
		}
		vector<int>dp(n + 1);
		dp[n] = 0;
		stack<int>st;
		for(int i = n - 1; i > -1; st.push(i--)){
			while(!st.empty() && a[st.top()] <= a[i]){
				st.pop();
			}
			dp[i] = dp[st.empty() ? n : st.top()] + 1;
		}
		cout << *max_element(dp.begin(), dp.end());
	}
}
namespace sub2{
	void solve(){
		vector<int>a(n);
		for(int& x : a){
			cin >> x;
		}
		vector<vector<int>>dp(n, vector<int>(n, -INF));
		for(int i = 0; i < n; i++){
			maximize(dp[i][i], 1);
			for(int j = i; j > -1; j--){
				for(int k = min(n - 1, i + d); k > i; k--){
					if(a[k] > a[j]){
						maximize(dp[k][k], dp[i][j] + 1);
					}
					else{
						maximize(dp[k][j], dp[i][j]);
					}
				}
			}
		}
		cout << *max_element(dp[n - 1].begin(), dp[n - 1].end());
	}
}
namespace sub3{
	void solve(){
		vector<int>a(n);
		for(int& x : a){
			cin >> x;
		}
		vector<int>dp(n, 1);
		for(int i = n - 2; i > -1; i--){
			for(int j = i + 1, pre = i; j < n && j - pre <= d; j++){
				if(a[j] > a[i]){
					maximize(dp[i], dp[j] + 1);
				}			
				else{
					pre = j;
				}	
			}
		}
		cout << *max_element(dp.begin(), dp.end());
	}
}
namespace sub6{
	void solve(){
		
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> d;
	if(n <= 20){
		sub1::solve();
	}
	else if(n <= 400){
		sub2::solve();
	}
	else if(n <= 7000){
		sub3::solve();
	}
	else if(d == 1){
		sub4::solve();
	}
	else if(d == n){
		sub5::solve();
	}
	else{
		sub6::solve();
	}
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:144:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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