Submission #1331554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1331554		nanaseyuzuki	Port Facility (JOI17_port_facility)	C++20	0 / 100	14 ms	31768 KiB

port_facility

#include <bits/stdc++.h>
// Kazusa_Megumi
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int n;
array <int, 2> a[mn];

namespace sub1{
    void backtrack(){
        int ans = 0;
        for(int mask = 0; mask < (1 << n); mask ++){
            vector <int> Kazuki, Maria;
            for(int i = 0; i < n; i++){
                if(mask & (1 << i)) Kazuki.push_back(i + 1);
                else Maria.push_back(i + 1);
            }

            int ok = 1;
            for(int i = Kazuki.size() - 1; i >= 1; i--){
                int cur = Kazuki[i], pre = Kazuki[i - 1];
                if(a[pre][0] < a[cur][0] && a[cur][0] < a[pre][1] && a[pre][1] < a[cur][1]) ok = 0;
            }

            for(int i = Maria.size() - 1; i >= 1; i--){
                int cur = Maria[i], pre = Maria[i - 1];
                if(a[pre][0] < a[cur][0] && a[cur][0] < a[pre][1] && a[pre][1] < a[cur][1]) ok = 0;
            }
            ans += ok;
        }
        cout << ans << '\n';
    }
}

namespace sub2 {
    bool check(int i, int j) {
        if(i == 0 || j == 0) return 1;
        return !(a[i][0] < a[j][0] && a[j][0] < a[i][1] && a[i][1] < a[j][1]);
    }

    int dp[2005][2005];

    int dfs(int u, int v){
        if(dp[u][v] != -1) return dp[u][v];
        int cur = max(u, v);
        if(cur == n) return 1ll;
        dp[u][v] = 0;
        if(check(u, cur + 1)) dp[u][v] += dfs(cur + 1, v);
        if(check(v, cur + 1)) dp[u][v] += dfs(u, cur + 1);
        dp[u][v] %= mod;
        return dp[u][v];
    }

    void calc() {
        dp[0][0] = 1ll;
        memset(dp, -1, sizeof(dp));
        cout << dfs(0, 0) << '\n';
    }
}

void solve() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i][0] >> a[i][1];
    sort(a + 1, a + n + 1);
    sub2::calc();
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("Kazuki.INP", "r")) {
        freopen("Kazuki.INP", "r", stdin);
        freopen("Kazuki.OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

port_facility.cpp:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main() {
      | ^~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         freopen("Kazuki.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
port_facility.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen("Kazuki.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22