STUPMACH Editorial

PROBLEM LINK:

Practice
Contest

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;
}

pretty weak test cases for STUPMACH…

For test case:
7
2 5 3 1 5 3 2
answer = 10.

https://www.codechef.com/viewsolution/28550108
gives 14 as result but got AC…

3 Likes

@arsenic_atg
Can you tell me what’s wrong with my code? The partial answer is correct but for the other one it’s showing WA. I didn’t read the solution above but pretty sure the concept is correct. Please have a look.

Solution link-Soln

1 Like

your method is absolutely correct. but in some of the statements like

> int sum=min*v.size();

your value of sum is going out of integers range, thats why it was not giving correct answer.

a simple fix is to use long long int instead of int.
corrected solution

@arsenic_atg How could you say its answer is 14? could be please explain?
According to me its answer is coming 10.

1 Like

you*

i think you are right the altered array is [2 2 2 1 1 1 1], instead of [2 3 5 1 1 1 1]. which yields correct answer as 10 not 14. my bad :sweat_smile: