Submission #1041579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041579		vjudge1	Segway (COI19_segway)	C++17	100 / 100	331 ms	24384 KiB

segway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define pf push_front
#define ep emplace_back
#define ef emplace_front
#define len(a) *(&a+1)-a  
// #define int long long
// #define ld long double
// #define mod 100ll000000007
#define stoi stoll
#define all(ls) ls.begin(),ls.end()
#define allr(ls) ls.rbegin(),ls.rend()
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
 
using namespace std;

using namespace __gnu_pbds;

template<typename type>using ordered_set=tree<type,null_type,less<type>,rb_tree_tag,tree_order_statistics_node_update>;
template<typename type>using ordered_multiset=tree<type,null_type,less_equal<type>,rb_tree_tag,tree_order_statistics_node_update>;

struct custom_hash{
	static uint64_t splitmix64(uint64_t x){
		x+=0x9e3779b97f4a7c15;
		x=(x^(x>>30))*0xbf58476d1ce4e5b9;
		x=(x^(x>>27))*0x94d049bb133111eb;
		return x^(x>>31);
	}
	size_t operator()(uint64_t x) const{
		static const uint64_t FIXED_RAnDOM=chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x+FIXED_RAnDOM);
	}
};

void solve(){
	int n;
	cin>>n;
	// multiset<int>ms;
	int ls[n][3],s[n],boost[n],k[n];
	for(int i=0;i<n;i++){
		s[i]=0;
		k[i]=0;
		boost[i]=0;
		cin>>ls[i][0]>>ls[i][1]>>ls[i][2];	
	}
	int m;
	cin>>m;
	int arr[m+1];
	int dp[m+1][n];
	memset(arr,0,sizeof(arr));
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=m;i++){
		cin>>arr[i];
		for(int j=0;j<n;j++){
			if(s[j]<=arr[i])
				dp[i][j]=dp[i-1][j]+(max(0,(min(100,arr[i])-s[j]))*ls[j][0]+max(0,(min(200,arr[i])-max(100,s[j])))*ls[j][1]+max(0,arr[i]-max(200,s[j]))*ls[j][2]);
			else
				dp[i][j]=dp[i-1][j]-s[j]+arr[i];
			k[j]=dp[i][j];
		}
		sort(k,k+n);
		for(int j=0;j<n;j++)
			boost[j]=(lower_bound(k,k+n,dp[i][j])-k)%20;
		for(int j=0;j<n;j++){
			if(s[j]<=arr[i]){
				s[j]=arr[i]+boost[j];
				dp[i][j]=dp[i][j]+boost[j];
			}
			else
				dp[i][j]=dp[i-1][j];
		}
	}
	for(int i=0;i<n;i++){
		if(s[i]<=300){
			dp[m][i]=dp[m][i]+(max(0,100-s[i])*ls[i][0]+max(0,200-max(100,s[i]))*ls[i][1]+max(0,300-max(200,s[i]))*ls[i][2]);
		}
		else
			dp[m][i]=dp[m][i]-(s[i]-300);
		cout<<dp[m][i]<<endl;

	}
	cout<<endl;
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr); 
	cout.tie(nullptr);
	// freopen("talent.in","r",stdin);
	// freopen("talent.out","w",stdout);
	int t=1;
	// cin>>t;
	while(t--){
		solve();
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45