Submission #1123493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123493		sixiyo7205	Tricks of the Trade (CEOI23_trade)	C++17	55 / 100	8106 ms	803296 KiB

trade

#include<bits/stdc++.h>
#define ll long long
#define pir pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn = 250009;
const ll inf = 1e17;

template <class t1,class t2> inline void mini(t1 &x,t2 y){if (x > y) x = y;}
template <class t1,class t2> inline void maxi(t1 &x,t2 y){if (x < y) x = y;}

int s[maxn],c[maxn];

void input(int n){
	for (int i = 1 ; i <= n ; i++) cin >> c[i];
	for (int i = 1 ; i <= n ; i++) cin >> s[i];
}

namespace subtask1{
	bool subtask1(int n,int k){
		return (n <= 200);
	}
	
	bool state[maxn];
	ll profit,pre[maxn];
	
	void prepare(int n,int k){
		profit = -inf;
		for (int i = 1 ; i <= n ; i++) pre[i] = pre[i - 1] + c[i];
		
		for (int L = 1 ; L <= n ; L++){
			priority_queue<int,vector<int>,greater<int>> pq;
			ll P = 0;
			
			for (int R = L ; R <= n ; R++){
				int x = s[R];
				
				P += x;
				pq.push(x);
				while (pq.size() > k){
					P -= pq.top();
					pq.pop();
				}
				
				if (pq.size() == k)
				   maxi(profit,P - (pre[R] - pre[L - 1])); 
			}
		}
		
		//doing exactly that again, but with s[i] >= pq.top
		for (int L = 1 ; L <= n ; L++){
			priority_queue<int,vector<int>,greater<int>> pq;
			ll P = 0;
			
			for (int R = L ; R <= n ; R++){
				int x = s[R];
				
				P += x;
				pq.push(x);
				while (pq.size() > k){
					P -= pq.top();
					pq.pop();
				}
				
				if (pq.size() == k && profit == P - (pre[R] - pre[L - 1])){
					int x = pq.top();
					
					for (int i = L ; i <= R ; i++)
					    state[i] |= (s[i] >= x);
				}
			}
		}
	}
	
	void solve(int n,int k){
		prepare(n,k);
		
		cout << profit << "\n";
		for (int i = 1 ; i <= n ; i++) cout << state[i];
	}
}

namespace subtask2{
	bool subtask2(int n,int k){
		return (n <= 6000);
	}

    const int NN = 6009;
    const int Zinf = 1e9 + 1e7;
    
    ll profit = -inf;
    bool state[maxn];
    
    int f[NN][NN];
	ll pre[NN];
	
	void prepare_f(int n){
		for (int i = 0 ; i <= n + 1; i++)
		   for (int j = 0 ; j <= n + 1 ; j++)
		      f[i][j] = Zinf;
	}
	
	void prepare_range(int n,int k){
		for (int L = 1 ; L <= n ; L++){
			priority_queue<int,vector<int>,greater<int>> pq;
			ll P = 0;
			
			for (int R = L ; R <= n ; R++){
				int x = s[R];
				
				P += x;
				pq.push(x);
				while (pq.size() > k){
					P -= pq.top();
					pq.pop();
				}
				
				if (pq.size() == k)
				   maxi(profit,P - (pre[R] - pre[L - 1])); 
			}
		}
		
		//doing exactly that again, but with s[i] >= pq.top
		for (int L = 1 ; L <= n ; L++){
			priority_queue<int,vector<int>,greater<int>> pq;
			ll P = 0;
			
			for (int R = L ; R <= n ; R++){
				int x = s[R];
				
				P += x;
				pq.push(x);
				while (pq.size() > k){
					P -= pq.top();
					pq.pop();
				}
				
				if (pq.size() == k && profit == P - (pre[R] - pre[L - 1]))
				    mini(f[L][R],pq.top());
			}
		}
	}
	
	void prepare(int n,int k){
		for (int i = 1 ; i <= n ; i++) pre[i] = pre[i - 1] + c[i];
		prepare_range(n,k);
		
		for (int len = n - 1 ; len >= 1 ; len--){
			for (int i = 1 ; i + len - 1 <= n ; i++){
				int l = i,r = i + len - 1;
				
				mini(f[l][r],f[l - 1][r]);
				mini(f[l][r],f[l][r + 1]);
			}
		}
		
		for (int i = 1 ; i <= n ; i++)
		   state[i] = (s[i] >= f[i][i]);
	}
	
	void solve(int n,int k){
		prepare_f(n);
		
		prepare(n,k);
		
        cout << profit << "\n";
		for (int i = 1 ; i <= n ; i++) cout << state[i];		
	}
}

namespace subtask3{
	bool subtask3(int n,int k){
		return (k == 2);
	}
	
	bool state[maxn];
	ll profit = -inf,pre[maxn];
	
	void upsolve(int n,int k){
		//preparing prefix sum of cost
		for (int i = 1 ; i <= n ; i++) pre[i] = pre[i - 1] + c[i];
		
		///
		ll P = -inf;
		for (int i = 1 ; i <= n ; i++){
			maxi(profit,P + (ll)s[i] - pre[i]);
			maxi(P,(ll)s[i] + pre[i - 1]);
		}
		
		//finding state,left to right
		P = -inf;
		for (int i = 1 ; i <= n ; i++){
			state[i] |= (P - pre[i]  +s[i]) == profit;
			maxi(P,(ll)s[i] + pre[i - 1]);
		}
		
		//right to left
		P = -inf;
		for (int i = n ; i > 0 ; i--){
			state[i] |= (P + s[i] + pre[i - 1]) == profit;
			maxi(P,s[i] - pre[i]);
		}
	}
	
	void solve(int n,int k){
		upsolve(n,k);
		
		cout << profit << "\n";
		for (int i = 1 ; i <= n ; i++) cout << state[i];
	}
}

namespace subtask4{
	bool subtask4(int n,int k){
		return (k <= 200);
	}
	const int maxk = 204;
	const ll inf = 1e17;
	
	ll dp[maxn][maxk][2],f[maxk],pre[maxn],profit = -inf;
	bool state[maxn];
	
	void prepare_dp(int n,int k){
		for (int i = 1 ; i <= n ; i++) pre[i] = pre[i - 1] + c[i];
		
		for (int i = 0 ; i <= n + 1 ; i++)
		   for (int j = 0 ; j <= k ; j++)
		      dp[i][j][0] = dp[i][j][1] = -inf;
	}
	
	void prepare_left(int n,int k){
		for (int i = 1 ; i <= k ; i++) f[i] = -inf;
		
		for (int i = 1 ; i <= n ; i++){
		    dp[i][1][0] = s[i] - c[i];
			
			for (int j = 2 ; j <= k ; j++)
			    if (f[j - 1] > -inf)
				   maxi(dp[i][j][0],f[j - 1] + s[i] - pre[i]);
			
			for (int j = 1 ; j <= k ; j++)
			    if (dp[i][j][0] > -inf)  
				  maxi(f[j],dp[i][j][0] + pre[i]);
			
			maxi(profit,dp[i][k][0]);
		}
	}
	
	void prepare_right(int n,int k){
		for (int i = 1 ; i <= k ; i++) f[i] = -inf;
		
		for (int i = n ; i > 0 ; i--){
		    dp[i][1][1] = s[i] - c[i];
			
			for (int j = 2 ; j <= k ; j++)
		      if (f[j - 1] > -inf)
			    maxi(dp[i][j][1],f[j - 1] + s[i] + pre[i - 1]);
			
			for (int j = 1 ; j <= k ; j++)
			    if (dp[i][j][1] > -inf)
			       maxi(f[j],dp[i][j][1] - pre[i - 1]);
		}
	}
	
	void prepare_state(int n,int k){
		f[0] = 0;
		for (int i = 1 ; i <= k ; i++) f[i] = -inf;
		
		for (int i = n ; i > 0 ; i--){
			for (int j = 1 ; j <= k ; j++)
			   state[i] |= (dp[i][j][0] + f[k - j] + pre[i]) == profit;
			
			for (int j = 1 ; j <= k ; j++)
			   maxi(f[j],dp[i][j][1] - pre[i - 1]);
			
			state[i] |= (dp[i][k][0] == profit);
			state[i] |= (dp[i][k][1] == profit);
		}
	}
	
	void solve(int n,int k){
	    prepare_dp(n,k);	
	    
	    prepare_left(n,k);
	    
	    prepare_right(n,k);
	    
	    prepare_state(n,k);
	    
	    cout << profit << "\n";
	    for (int i = 1 ; i <= n ; i++) cout << state[i];
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
//	freopen("TRADE.inp","r",stdin);
//	freopen("TRADE.out","w",stdout);
	
	int n,k;
	cin >> n >> k;
	input(n);
	
  if (subtask1::subtask1(n,k)){
		subtask1::solve(n,k);
		return 0;
   }
	
	if (subtask2::subtask2(n,k)){
		subtask2::solve(n,k);
		return 0;
	}
	
	if (subtask3::subtask3(n,k)){
		subtask3::solve(n,k);
		return 0;
	}
	
	subtask4::solve(n,k);
	

	return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 0 / 45