oj.uz

Submission #1041574

# Submission time Handle Problem Language Result Execution time Memory
1041574 2024-08-02T05:55:16 Z vjudge1 Segway (COI19_segway) C++17
15 / 100
 21 ms 1128 KB 
#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];
	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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 21 ms 1128 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 600 KB Output is correct
5 Correct 21 ms 1128 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Halted 0 ms 0 KB -