Submission #1143951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143951		SmuggingSpun	Semiexpress (JOI17_semiexpress)	C++20	48 / 100	32 ms	584 KiB

semiexpress

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
const ll INF = 1e18;
template<class T>void maximize(T& a, T b){
	if(a < b){
		a = b;
	}
}
int n, m, k, A, B, C;
ll T;
namespace sub1{
	void solve(){
		vector<bool>express(n + 1, false);
		for(int _ = 0; _ < m; _++){
			int x;
			cin >> x;
			express[x] = true;
		}	
		int ans = 0;	
		for(int i = 1; i < n; i++){
			for(int j = n; j > i; j--){
				if(!express[i] && !express[j]){
					int cnt = 0;
					for(int t = 2, pre = 1; t <= n; t++){
						if(express[t]){
							pre = t;
						}
						if(1LL * (pre - 1) * B + min(1LL * (t - pre) * A, min(i >= pre && i <= t ? 1LL * (i - pre) * C + 1LL * (t - i) * A : INF, j >= pre && j <= t ? 1LL * (j - pre) * C + 1LL * (t - j) * A : INF)) <= T){
							cnt++;
						}
					}
					maximize(ans, cnt);
				}
			}
		}
		cout << ans;
	}
}
namespace sub2{
	void solve(){
		vector<int>near(n + 1);
		for(int _ = 0, pre = 1, cur; _ < m; _++, pre = cur){
			cin >> cur;
			for(int i = (near[cur] = cur) - 1; i > pre; i--){
				near[i] = pre;
			}
		}
		vector<vector<int>>dp(n + 2, vector<int>((k -= m) + 1, 0));
		for(int i = 1; i <= n; i++){
			for(int j = 0; j <= k; j++){
				for(int t = i, cnt = 0; t <= n; t++){
					if(1LL * (near[t] - 1) * B + 1LL * (t - near[t]) * A <= T){
						cnt++;
					}
					maximize(dp[t + 1][j], dp[i][j] + cnt);
				}
				if(j > 0){
					for(int t = i, cnt = 0; t <= n; t++){
						if(1LL * (near[t] - 1) * B + (near[t] < i ? 1LL * (i - near[t]) * C + 1LL * (t - i) * A : 1LL * (t - near[t]) * A) <= T){
							cnt++;	
						}
						maximize(dp[t + 1][j - 1], dp[i][j] + cnt);
					}
				}
			}
		}
		cout << dp[n + 1][0] - 1;
	}
}
namespace sub3{
	void solve(){
		vector<int>ex(m);
		for(int& x : ex){
			cin >> x;
		}
		int ans = int(1LL * B * (n - 1) <= T) - 1;
		vector<int>item;
		k -= m;
		for(int i = 0; i + 1 < m; i++){
			for(int j = -1, p = ex[i]; j < k && p < ex[i + 1]; j++){
				ll remain = T - 1LL * B * (ex[i] - 1) - 1LL * C * (p - ex[i]);
				if(remain < 0){
					break;
				}
				int cnt = ex[i + 1] - p - 1;
				if(remain / A >= cnt){
					if(j == 0){
						ans += cnt + 1;
					}
					else{
						item.emplace_back(cnt + 1);
					}
					break;
				}
				if(j == 0){
					ans += remain / A + 1;
				}
				else{
					item.emplace_back(remain / A + 1);
				}
				p += remain / A + 1;
			}			
		}
		sort(item.begin(), item.end(), greater<int>());
		for(int i = min(int(item.size()), k) - 1; i > -1; i--){
			ans += item[i];
		}
		cout << ans;
	}
}
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 >> m >> k >> A >> B >> C >> T;
	if(n <= 300 && k - m == 2){
		sub1::solve();
	}
	else if(n <= 300){
		sub2::solve();
	}
	else{
		sub3::solve();
	}
}

Compilation message (stderr)

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

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 0 / 52