oj.uz

Submission #643674

# Submission time Handle Problem Language Result Execution time Memory
643674 2022-09-22T18:27:53 Z Richem Snowball (JOI21_ho_t2) C++14
100 / 100
 578 ms 15316 KB 
#include <iostream>
#include <vector>
#define int long long
using namespace std;

const int MAX_NOMBRE = 2e5+42, INF = 1e13;

int nbBoule, nbVent;

int pos[MAX_NOMBRE];
int vent[MAX_NOMBRE][2] = {0};

int rep[MAX_NOMBRE][2] = {0};

void input() {
    cin >> nbBoule >> nbVent;

    for(int i = 0; i < nbBoule; i++)
        cin >> pos[i];

    int cumul = 0;
    for(int i = 0; i < nbVent; i++) {
        int curVent;
        cin >> curVent;

        cumul += curVent;

        if(i > 0) {
            vent[i][0] = min(vent[i-1][0], cumul);
            vent[i][1] = max(vent[i-1][1], cumul);
        }
        else {
            if(cumul < 0) vent[i][0] = cumul;
            else vent[i][1] = cumul;
        }
    }

    rep[0][0] = -vent[nbVent-1][0];
    rep[nbBoule-1][1] = vent[nbVent-1][1];
}


bool possible(int idBoule, int curEtape, int cote) {
    if((cote == 0 && idBoule == 0) || (cote == 1 && idBoule == nbBoule-1)) 
        return 1;

    //cout << curEtape << " COTE \n";

    //if(idBoule == 1 && curEtape == 0 && cote == 1) cout << " YIOUPU";

    int bordCur = pos[idBoule] + vent[curEtape][cote];
    int diff[2] = {-1, 1};

    int idAutre = idBoule + diff[cote];

    int bordAutre = pos[idAutre] + vent[curEtape][1 - cote];

    if(cote == 0) {
        rep[idBoule][cote] = max(rep[idBoule][cote], pos[idBoule] - max(bordCur, bordAutre));
    }
    else {
        rep[idBoule][cote] = max(rep[idBoule][cote], min(bordCur, bordAutre) - pos[idBoule]);
        //cout << rep[idBoule][cote] << " REP \n";
    }

    //cout << pos[idBoule] << " " << bordCur << " " << pos[idBoule + diff[cote]] << " " << bordAutre << endl;

    bool ok = ((max(bordAutre, pos[idAutre]) <= min(pos[idBoule], bordCur)) || (max(bordCur, pos[idBoule]) <= min(pos[idAutre], bordAutre)));

    return ok;
}

void dicho(int idBoule, int cote) {
    int deb = 0, fin = nbVent-1;

    int ah = 0;

    while(deb <= fin) {
        int milieu = (deb + fin+1) / 2;

        if(possible(idBoule, milieu, cote)) 
            deb = milieu;
        else
            fin = milieu-1;

        if(deb == fin) {
            ah++;
            if(ah > 1) return;
        }
    }
}

signed main() {
    input();

    /*
    dicho(1, 1);
    return 0;
    while(1) {
        int a,b,c;
        cin >> a >> b >> c;

        cout << possible(a,b,c) << endl;
    }
    */


    for(int cur = 0; cur < nbBoule; cur++) {
        dicho(cur, 0);
        dicho(cur, 1);

        cout << rep[cur][0] + rep[cur][1] << endl;
    }
}

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 448 KB Output is correct
8 Correct 5 ms 340 KB Output is correct
9 Correct 4 ms 444 KB Output is correct
10 Correct 5 ms 316 KB Output is correct
11 Correct 4 ms 428 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 6 ms 468 KB Output is correct
16 Correct 7 ms 468 KB Output is correct
17 Correct 5 ms 448 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 5 ms 316 KB Output is correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 5 ms 448 KB Output is correct
8 Correct 5 ms 340 KB Output is correct
9 Correct 4 ms 444 KB Output is correct
10 Correct 5 ms 316 KB Output is correct
11 Correct 4 ms 428 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 6 ms 468 KB Output is correct
16 Correct 7 ms 468 KB Output is correct
17 Correct 5 ms 448 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 5 ms 316 KB Output is correct
20 Correct 84 ms 5544 KB Output is correct
21 Correct 76 ms 5264 KB Output is correct
22 Correct 72 ms 5096 KB Output is correct
23 Correct 67 ms 5032 KB Output is correct
24 Correct 100 ms 5580 KB Output is correct
25 Correct 507 ms 13456 KB Output is correct
26 Correct 501 ms 13280 KB Output is correct
27 Correct 492 ms 13032 KB Output is correct
28 Correct 540 ms 13128 KB Output is correct
29 Correct 487 ms 12640 KB Output is correct
30 Correct 460 ms 11996 KB Output is correct
31 Correct 473 ms 11440 KB Output is correct
32 Correct 418 ms 11652 KB Output is correct
33 Correct 56 ms 1572 KB Output is correct
34 Correct 500 ms 13740 KB Output is correct
35 Correct 490 ms 13120 KB Output is correct
36 Correct 514 ms 13468 KB Output is correct
37 Correct 481 ms 13092 KB Output is correct
38 Correct 526 ms 13068 KB Output is correct
39 Correct 493 ms 13284 KB Output is correct
40 Correct 479 ms 13224 KB Output is correct
41 Correct 99 ms 6172 KB Output is correct
42 Correct 410 ms 11544 KB Output is correct
43 Correct 473 ms 14948 KB Output is correct
44 Correct 96 ms 5948 KB Output is correct
45 Correct 421 ms 13140 KB Output is correct
46 Correct 506 ms 15052 KB Output is correct
47 Correct 578 ms 15192 KB Output is correct
48 Correct 493 ms 15316 KB Output is correct