제출 #1201983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1201983		negart	Restore Array (RMI19_restore)	C++20	100 / 100	384 ms	824 KiB

restore

// ~ be name khoda ~ //

#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 5e3 + 10;
const int MAX_M = 1e4 + 10;

vector <tuple<int, int, int>> e;
int n, m, dis[2][MAX_N], ans[MAX_N];

bool check() {
    for(int i = n + 1; i <= 2 * n; i++) {
        for(int j = 0; j < e.size(); j++) {
            auto [v, u, w] = e[i];
            dis[i & 1][u] = min({dis[i & 1][u], dis[(i - 1) & 1][u], dis[(i - 1) & 1][v] + w});
            if(dis[i & 1][u] != dis[(i - 1) & 1][u])
                return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    memset(dis, 63, sizeof dis);
    for(int i = 0; i < m; i++) {
        int l, r, k, val;
        cin >> l >> r >> k >> val;
        l++;
        r++;
        if(val == 0) {
            e.push_back({l - 1, r, r - l + 1 - k});
        }
        else {
            e.push_back({r, l - 1, -r + l - 2 + k});
        }
    }

    for(int i = 0; i < n; i++) {
        e.push_back({i, i + 1, 1});
        e.push_back({i + 1, i, 0});
    }

    dis[0][0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < e.size(); j++) {
            auto [v, u, w] = e[j];
            dis[i & 1][u] = min({dis[i & 1][u], dis[(i - 1) & 1][u], dis[(i - 1) & 1][v] + w});
        }
    }
    if(check()) {
        cout << -1 << endl;
        return 0;
    }
    else {
        cout << dis[n&1][1] << " ";
        for(int i = 2; i <= n; i++) {
            if(dis[n & 1][i] == dis[n & 1][i - 1])
                cout << 0 << " ";
            else if(dis[n & 1][i] > dis[n & 1][i - 1])
                cout << 1 << " ";
            else
                cout << 0 << " ";
        }
    }
}

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