PROBLEM LINK:
Tester: Roman Bilyi
Editorialist: Hussain Kara Fallah
PROBLEM EXPLANATION
There are N boxes in a line (numbered 1 through N). Initially, the boxes are empty, and I need to use the machine to put tokens in them. For each valid i, the i_{th} box has a maximum capacity S_i tokens. I can perform the following operation any number of times: choose an integer L (1≤L≤N) and put one token in each of the boxes 1,2,…,L.
You must put as many tokens as possible into the boxes in total (the distribution of tokens in the boxes does not matter). Of course, it is not allowed to perform an operation that would result in a number of tokens in any box exceeding its capacity. Can you help to calculate the maximum number of tokens that can be put in these boxes?
DIFFICULTY:
Easy
CONSTRAINTS
1 \leq |N| \leq 10^6
EXPLANATION:
In the optimal solution, the maximum number of tokens that will be put in the i_{th} box would be \{min\, S_j\} among all j (1 \leq j \leq i).
The operation that we can perform is very limited, in order to put some token in i_{th} box you must put a token in every box behind it. So the number of tokens inside it mustn’t ever exceed the capacity of any box behind it.
After determining the maximum number of tokens we can put in each box, our answer is simply the sum.
Check the implementation for more details.
Editorialist solution
#include <bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
long long n , x , ans;
cin>>n>>x;
ans = x;
for(int j = 1 ; j < n ; j++){
long long q;
cin>>q;
x = min(q , x);
ans += x;
}
cout<<ans<<endl;
}
}
Tester Solution
#include <bits/stdc++.h>
#define ll int64_t
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sc second
#define fr first
using namespace std;
const int N = 2e6+100;
int main(){
int t;
cin>>t;
while(t--){
int n;
scanf("%d",&n);
int a;
ll res =0;
int mn = 2e9;
for(int i=0 ;i <n ;i ++){
scanf("%d",&a);
mn = min(mn,a);
res += mn;
}
printf("%lld\n",res);
}
return 0;
}