CSES - HIIT Open 2024 - Results
Submission details
Task:Key cutting
Sender:CPLX
Submission time:2024-11-16 14:22:42 +0200
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#60.00 sdetails
#70.00 sdetails
#80.00 sdetails
#9ACCEPTED0.02 sdetails
#10--details
#11--details
#12--details
#13--details
#14--details

Code

#include<iostream>
#include<vector>
typedef long long ll;
using namespace std;

void decrease(vector<ll>& key, ll a, ll b, ll minim){
    for(ll i=a; i<=b; i++){
        key[i] -= minim;
    }
    
}

int main(){
    ll n;
    cin >> n;
    vector<ll> key(n);

    for(ll i = 0; i < n; ++i) cin >> key[i];

    ll start = -1;
    ll minim;

    ll op = 0;
    for(ll i = 0; i < n; i++){
        if(start == -1 and key[i]!=0){
            start = i;
            minim = key[i];
        }

        if(start!=-1 and (key[i]==0 or i==n-1)){
            //cout << "jansdjkak" << endl;
            // cout << minim << "aksdjla" << endl;
            if(key[i]==0) decrease(key,start,i-1,minim);
            else decrease(key,start,i,minim);
            start = -1;
            op +=1;
            i=0;

        }
        if(start!=-1 and key[i]<minim) minim = key[i];

    }
    cout << op << endl;
    

}

/*1 3 2 4 1
0 2 1 3 0
0 1 0 2 0
0 0 0 2 0
0 0 0 0 0
*/

Test details

Test 1

Verdict: ACCEPTED

input
3
1 2 1

correct output
2

user output
2

Test 2

Verdict: ACCEPTED

input
1
0

correct output
0

user output
0

Test 3

Verdict: ACCEPTED

input
1
9

correct output
1

user output
1

Test 4

Verdict: ACCEPTED

input
100
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
0

user output
0

Test 5

Verdict: ACCEPTED

input
100
0 0 0 1 1 0 0 0 0 1 1 1 0 1 1 ...

correct output
25

user output
25

Test 6

Verdict:

input
100
2 1 2 1 2 0 0 0 1 1 2 2 1 2 2 ...

correct output
41

user output
40

Test 7

Verdict:

input
100
36 5 10 37 94 59 20 31 64 2 58...

correct output
99

user output
98

Test 8

Verdict:

input
100
228768416 32415139 952687252 6...

correct output
100

user output
99

Test 9

Verdict: ACCEPTED

input
100000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

correct output
0

user output
0

Test 10

Verdict:

input
100000
1 1 1 0 0 1 0 0 0 0 1 0 1 0 0 ...

correct output
24965

user output
(empty)

Test 11

Verdict:

input
100000
2 1 2 2 2 2 2 1 1 0 1 1 0 1 1 ...

correct output
38968

user output
(empty)

Test 12

Verdict:

input
100000
4 4 5 4 4 5 0 2 2 1 4 4 1 0 5 ...

correct output
59156

user output
(empty)

Test 13

Verdict:

input
100000
18 5 6 16 8 10 1 7 4 15 5 9 19...

correct output
82598

user output
(empty)

Test 14

Verdict:

input
100000
33 37 37 86 42 38 18 10 77 57 ...

correct output
94897

user output
(empty)