Submission #1328062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1328062		horiaboeriu	Restore Array (RMI19_restore)	C++20	100 / 100	125 ms	652 KiB

restore

#include <iostream>

using namespace std;
const int MAXN = 5000;
const int MAXM = 10000;
const int INF = 1e9;
int sp[MAXN + 1], vx[MAXM + 2 * MAXN], vy[MAXM + 2 * MAXN], vc[MAXM + 2 * MAXN];
int nrm;
void adaug(int x, int y, int cost) {
    vx[nrm] = x;
    vy[nrm] = y;
    vc[nrm] = cost;
    nrm++;
}
int minim(int a, int b) {
    return a < b ? a : b;
}
int main()
{
    int n, m, l, r, k, val, i, j;
    scanf("%d%d", &n, &m);
    //trebuie sa respect toate aceste conditii
    //daca am sp[x] <= sp[y] + val atunci pun muchie de la y la x de cost val si sp[x] = min(sp[x], sp[y] + val)
    //ca practic o sa aleg maximul care respecta toate conditiile adica aleg minimul dintre maximul care respecta conditiile anterioare si cel de acum
    //si dupa trebuie sa nu am ciclu negativ si asat verific cu bellman ford sa nu se mai schimbe sp-uri dupa n iteratii
    for (i = 0; i < m; i++) {
        scanf("%d%d%d%d", &l, &r, &k, &val);
        l++;
        r++;
        if (val == 0) {
            //al k-lea este 0 deci dintre cele (r - l + 1) numere sunt minim k de 0 deci maxim (r - l + 1) - k de 1
            //sp[r] - sp[l - 1] <= (r - l + 1) - k
            //deci sp[r] <= sp[l - 1] + (r - l + 1) - k
            adaug(r, l - 1, (r - l + 1) - k);
        } else {
            //al k-lea este 1 deci dintre cele (r - l + 1) numere sunt maxim k - 1 de 0 deci minim (r - l + 1) - k + 1 de 1
            //sp[r] - sp[l - 1] >= (r - l + 2) - k
            //sp[r] - (r - l + 2) + k >= sp[l - 1]
            //sp[l - 1] <= sp[r] - (r - l + 2) + k
            adaug(l - 1, r, -(r - l + 2) + k);
        }
    }
    sp[0] = 0;
    for (i = 1; i <= n; i++) {
        //sp[i] <= sp[i - 1] + 1
        //si sp[i] >= sp[i - 1] deci sp[i - 1] <= sp[i]
        //ca fiecare valoare din vector este de la 0 la 1
        adaug(i, i - 1, 1);
        adaug(i - 1, i, 0);
        sp[i] = INF;
    }
    for (i = 0; i < n; i++) {
        for (j = 0; j < nrm; j++) {
            sp[vx[j]] = minim(sp[vx[j]], sp[vy[j]] + vc[j]);
        }
    }
    j = 0;
    while (j < nrm && sp[vx[j]] <= sp[vy[j]] + vc[j]) {
        j++;
    }
    if (j < nrm) {
        printf("-1\n");//am ciclu negativ in graf
    } else {
        for (i = 1; i <= n; i++) {
            printf("%d ", sp[i] - sp[i - 1]);
        }
        printf("\n");
    }
    return 0;
}

Compilation message (stderr)

restore.cpp: In function 'int main()':
restore.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     scanf("%d%d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~
restore.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d%d%d%d", &l, &r, &k, &val);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55