Submission #1253968

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253968		nerrrmin	Fire (BOI24_fire)	C++20	31 / 100	29 ms	6984 KiB

Main

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
using namespace std;
const long long maxn = 905;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, m;
long long s[maxn], e[maxn];
map < long long, long long > mp;
vector < long long > u;

vector < long long > g[maxn];
int dp[maxn][maxn];
int over[maxn][maxn];
int pref[maxn][maxn];
vector < pair < int, int > > day, night;
int main()
{
    speed();

    cin >> n >> m;
    for (long long i = 1; i <= n; ++ i)
    {
        cin >> s[i] >> e[i];
        u.pb(s[i]);
        u.pb(e[i]);
    }
    u.pb(0);
    u.pb(m);
    sort(u.begin(), u.end());
    int cnt = 0, last = -1;
    for (auto x: u)
    {
        if(x != last)
        {
            cnt ++;
            mp[x] = cnt;
        }
        last = x;
    }
    int lt = mp[0], rt = mp[m];
    for (int i = 1; i <= n; ++ i)
    {
        s[i] = mp[s[i]];
        e[i] = mp[e[i]];
    }
    for (int i = 0; i <= rt + 10; ++ i)
    {
        for (int j = 0; j <= rt + 10; ++ j)
        {
            dp[i][j] = 1e9;
            over[i][j] = 1e9;
            pref[i][j] = 1e9;
        }
    }
    for (int i = 1; i <= n; ++ i)
    {
        if(s[i] <= e[i])
        {
            day.pb({s[i], e[i]});
            dp[s[i]][e[i]] = 1;
        }
        else
        {
            night.pb({e[i], s[i]});
            over[e[i]][s[i]] = 1;
        }
    }

    for (int len = 1; len <= rt; ++ len)
    {
        for (int i = lt; i <= rt; ++ i)
        {
            int j = i + len - 1;

           // cout << i << " " << j << " - > " << dp[i][j] << endl;
            if(j > rt)continue;
            if(dp[i][j] == 1e9)continue;
            for (auto &[l, r]: day)
            {
                if(r < i || l > j)continue;
                int rangel = min(l, i);
                int ranger = max(j, r);
                dp[rangel][ranger] = min(dp[rangel][ranger], dp[i][j] + 1);
            }
           // cout << dp[i][j] << endl;
        }
    }

    for (int i = 1; i <= rt; ++ i)
    {
        for (int j = rt; j >= 1; -- j)
        {
           // cout << i << " " << j << " -> " << over[i][j] << endl;
            if(over[i][j] == 1e9)continue;
            for (auto &[l, r]: night)
            {
                int rangel = max(l, i);
                int ranger = min(j, r);
                over[rangel][ranger] = min(over[rangel][ranger], over[i][j] + 1);
            }
        }
    }

    for (int len = rt; len >= 1; -- len)
    {
        for (int i = 1; i <= rt; ++ i)
        {
            int j = i + len - 1;
            if(j > rt)continue;
            pref[i][j] = min(min(pref[i][j], pref[i-1][j]), dp[i][j]);
            if(j < rt)pref[i][j] = min(pref[i][j], pref[i][j+1]);

            //cout << i << " " << j << " pref is " << pref[i][j] << endl;
        }
    }
    int ans = 1e9;
    for (int i = 1; i <= rt; ++ i)
    {
        for (int j = 1; j <= rt; ++ j)
        {
            //cout << i << " " << j << " anddd " << pref[i][j] << endl;
            ans = min(ans, pref[i][j] + over[i][j]);
        }
    }
    if(ans == 1e9)cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 0 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26