Submission #1169351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169351		mertbbm	Segway (COI19_segway)	C++20	100 / 100	427 ms	1640 KiB

segway

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

array<int,3>f(int a){
	//how many a, how many b, how many c
	array<int,3>temp;
	temp[0]=min(100LL,a);
	temp[1]=min(100LL,a-100LL);
	temp[2]=min(100LL,a-200LL);
	temp[1]=max(0LL,temp[1]);
	temp[2]=max(0LL,temp[2]);
	return temp;
}

void solve(){
	int n;
	cin >> n;
	array<int,3>arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x][0] >> arr[x][1] >> arr[x][2];
	}
	
	int m;
	cin >> m;
	int take[m+1];
	for(int x=0;x<m;x++){
		cin >> take[x];
	}
	take[m]=300;
	
	pii storage[n];
	for(int x=0;x<n;x++){
		array<int,3>hold=f(take[0]);
		storage[x].first=hold[0]*arr[x][0]+hold[1]*arr[x][1]+hold[2]*arr[x][2];
		storage[x].second=0;
	}
	
	for(int x=0;x<m;x++){
		vector<int>v;
		for(int y=0;y<n;y++){
			v.push_back(storage[y].first);
		}
		sort(v.begin(),v.end());
		
		for(int y=0;y<n;y++){
			int boost=lower_bound(v.begin(),v.end(),storage[y].first)-v.begin();
			boost%=20;
			if(storage[y].second!=0) boost=storage[y].second;
			//recalculate
			int a=min(take[x+1]-take[x],boost);
			int nxt=boost-a;
			array<int,3>hold=f(take[x]+a);
			array<int,3>hold2=f(take[x+1]);
			hold[0]=hold2[0]-hold[0];
			hold[1]=hold2[1]-hold[1];
			hold[2]=hold2[2]-hold[2];
			
			storage[y].first+=a+hold[0]*arr[y][0]+hold[1]*arr[y][1]+hold[2]*arr[y][2];
			storage[y].second=nxt;
		}
	}
	
	for(int x=0;x<n;x++){
		cout << storage[x].first << "\n";
	}
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("cowdate.in","r",stdin);
	//freopen("cowdate.out","w",stdout);
	int t=1;
	//cin >> t;	
	while(t--){
		solve(); 
	}
}

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