fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #include <ext/pb_ds/assoc_container.hpp> 
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds; 
  6. #define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  7. #pragma GCC optimize "trapv"
  8. #define _GLIBCXX_DEBUG
  9. #define ll long long int
  10. #define ld long double
  11. #define ull unsigned long long int  // ranges from (0 - twice of long long int)
  12. #define rep(i,a,n) for (ll i=a;i<n;i++)
  13. #define per(i,a,n) for (ll i=n-1;i>=a;i--)
  14. #define pb push_back
  15. #define mp make_pair
  16. #define vll vector<ll>
  17. #define mod 1000000007LL
  18. #define llpair pair<ll,ll>
  19. #define INF 1000000000000000000ll
  20. #define np next_permutation
  21. #define PI acos(-1)
  22. #define deb(x) cout<<#x<<" "<<x<<endl;
  23. #define rotate_left(vec,amt) rotate(vec.begin(),vec.begin()+amt,vec.end());
  24. #define rotate_right(vec,amt) rotate(vec.begin(),vec.begin()+vec.size()-amt,vec.end());
  25. #define all(x) x.begin(),x.end()
  26. #define sortall(x) sort(all(x))
  27. #define clr(x) memset(x,0,sizeof(x))
  28. typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> pbds;
  29.  
  30. // It doesn't matter how Slowly you go,as long as you do not stop.
  31. // What is my Aim:->(SELF SATISFACTION that I have done my BEST).
  32.  
  33. struct custom_hash {
  34.     static uint64_t splitmix64(uint64_t x) {
  35.         // http://x...content-available-to-author-only...i.it/splitmix64.c
  36.         x += 0x9e3779b97f4a7c15;
  37.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  38.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  39.         return x ^ (x >> 31);
  40.     }
  41.  
  42.     size_t operator()(uint64_t x) const {
  43.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  44.         return splitmix64(x + FIXED_RANDOM);
  45.     }
  46. };
  47.  
  48. // This is used when We want to use pairs in unordered_map and unordered_set
  49. struct pair_hash
  50. {
  51.     template <class T1, class T2>
  52.     std::size_t operator() (const std::pair<T1, T2> &pair) const
  53.     {
  54.         return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
  55.     }	
  56. };
  57.  
  58.  
  59. bool check(ll mid, ll arr[], ll n, ll pre[], ll k)
  60. {
  61. 	for(ll i=1;i<n;i++)
  62. 	{
  63. 		ll curr_prefix= pre[i-1] + mid;
  64. 		if((double)curr_prefix/arr[i]>=(double)100/k)
  65. 		continue;
  66. 		else
  67. 		return false;
  68. 	}
  69.  
  70. 	return true;
  71. }
  72.  
  73. int main() {
  74.     auto start = chrono::high_resolution_clock::now();
  75.     fio;
  76.     ll t=1; 
  77.     cin>>t;
  78. 	while(t--)
  79. 	{
  80. 		ll n,k; cin>>n>>k;
  81.  
  82. 		ll arr[n]; rep(i,0,n) cin>>arr[i];
  83.  
  84. 		ll pre[n];
  85. 		pre[0]=arr[0];
  86. 		for(int i=1;i<n;i++)
  87. 		pre[i]=pre[i-1] + arr[i];
  88.  
  89.  
  90. 		ll low=0;
  91. 		ll high=1e18;
  92.  
  93.  
  94. 		while(low<high)
  95. 		{
  96. 			ll mid = (low) + (high-low)/2;
  97. 			if(check(mid,arr,n,pre,k))
  98. 			high=mid;
  99. 			else
  100. 			low=mid;
  101.  
  102. 			if(high-low==1) break;
  103. 		}
  104.  
  105. 		if(check(low,arr,n,pre,k))
  106. 		cout<<low<<"\n";
  107. 		else
  108. 		cout<<high<<"\n";
  109.  
  110. 	}
  111.  
  112.     auto finish = chrono::high_resolution_clock::now();
  113.     cerr << "Time elapsed: " << (chrono::duration<long double>(finish-start)).count() << "s\n";
  114.     return 0;
  115.  
  116. }
  117.  
  118.  
Success #stdin #stdout #stderr 0s 4776KB
comments (?)
stdin
copy 
2
4 1
20100 1 202 202
3 100
1 1 1
stdout
copy 
99
0
stderr
copy 
Time elapsed: 5.3316e-05s
https://ideone.com/07dh2T
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!