oj.uz

Submission #630659

# Submission time Handle Problem Language Result Execution time Memory
630659 2022-08-16T20:43:08 Z inksamurai Kvalitetni (COCI16_kvalitetni) C++17
120 / 120
 9 ms 2536 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3phCa4T ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

signed main(){
_3phCa4T;
	int n;
	cin>>n;
	vi a(n);
	rep(i,n){
		cin>>a[i];
	}
	string s;
	cin>>s;
	const int m=sz(s);
	vi rp(m);
	vi stk;
	rep(i,m){
		if(s[i]=='('){
			stk.pb(i);
		}else if(s[i]==')'){
			rp[stk.back()]=i;
			stk.pop_back();
		}
	}
	assert(rp[0]);
	using ld=long double;
	auto dfs=[&](auto self,int l,int r)->ld{
		if(l==r-2){
			return a[0];
		}
		vec(ld) rbts;
		char expr;
 		for(int i=l+1;i<r;i++){
			if(s[i]=='('){
				rbts.pb(self(self,i,rp[i]));
				i=rp[i];
			}else{
				expr=s[i];
			}
		}
		ld sun=0;
		for(auto v:rbts){
			sun+=v;
		}
		// if(l==1 and r==9) print("ho",sz(rbts),expr,sun);
		ld need=a[sz(rbts)-1];
		if(expr=='+'){
			return min(need,sun);
		}
		// print(l,r,need,sz(rbts));
		if(sun<=need){
			//
		}else{
			sort(rbts.rbegin(), rbts.rend());
			ld x=rbts[0];
			rng(i,1,sz(rbts)+1){
				if(i<sz(rbts) and sun-(x-rbts[i])*i>=need){
					sun-=(x-rbts[i])*i;
					x=rbts[i];
				}else{
					rep(j,i){
						rbts[j]=x;
					}
					//sun-k*i=need
					//sun-need=k*i
					//(sun-need)/i
					ld k=(sun-need)/i;
					rep(j,i){
						rbts[j]-=k;
					}
					break;
				}
			}
		}
		ld _prod=1;
		for(auto v:rbts){
			_prod*=v;
		}
		return _prod;
	};
	cout<<fixed<<setprecision(16);
	ld res=dfs(dfs,0,rp[0]);
	print(res);
}

Compilation message

kvalitetni.cpp: In lambda function:
kvalitetni.cpp:62:3: warning: 'expr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |   if(expr=='+'){
      |   ^~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 324 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 1652 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 6 ms 1760 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1364 KB Output is correct
2 Correct 7 ms 2536 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 9 ms 2408 KB Output is correct