oj.uz

Submission #943804

# Submission time Handle Problem Language Result Execution time Memory
943804 2024-03-12T01:14:48 Z Boycl07 Boat (APIO16_boat) C++17
9 / 100
 1403 ms 7064 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define FORD(i, n) for(int i = n - 1; i >= 0; --i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task "boat"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}


const int N =  1e3 + 10;
const int M = 1e3 + 3;
const int N1 = 2e3 + 10;
const int K = 1e2 + 1;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll LINF = 1e17 + 2;
const int block_size = 500;
const int LOG = 40;
const int offset = N;
const int LIM = 11 ;
const int AL = 26;

int add(int x, int y)
{
    x += y;
    if(x >= MOD) x -= MOD;
    if(x < 0) x += MOD;
    return x;
}

int mul(int x, int y)
{
    return 1ll * x * y % MOD;
}

int n;

int a[N], b[N];

int C[N][N];

int comb[N], inv[N];

int dp[N][N];

vector<int> zip;

void solve()
{
    cin >> n;
    rep(i, n)
    {
        cin >> a[i] >> b[i];
        zip.pb(a[i]);
        zip.pb(b[i] + 1);
    }
    sort(all(zip));
    zip.resize(unique(all(zip)) - zip.begin());
    rep(i, n) rep(j, n) C[i][j] = add(C[i - 1][j], C[i][j - 1]);

//    rep(i, n) a[i] = upper_bound(all(zip), a[i]) - zip.begin();
//    rep(i, n) b[i] = upper_bound(all(zip), b[i]) - zip.begin();

    int m = sz(zip);
    dp[0][0] = 1;
    inv[0] = inv[1] = 1;
    forn(i, 2, 2 * n) inv[i] = add(MOD, -mul(inv[MOD % i], MOD / i));
    forn(i, 0, m - 1)
    {
        int l, r;
        l = zip[i], r = i == m - 1 ? zip[i] + 1 : zip[i + 1];
        forn(j, 0, n)
        {
            dp[i + 1][j] = add(dp[i + 1][j], dp[i][j]);
            int cnt = 0, cur = 1;
            comb[0] = 0;
            forn(k, 1, n)
            {
                cur = mul(cur, mul(inv[k - 1], r - l - k + 1));
                comb[k] = add(comb[k - 1], cur);
            }
            forn(k, j + 1, n)
            {
                if(a[k] <= l && b[k] >= r - 1)
                {
                    dp[i + 1][k] = add(dp[i + 1][k], mul(dp[i][j], comb[++cnt]));
                }
            }
        }
    }
//    rep(i, m)
//    {
//        rep(j, n) cout << i << " " << j << endl << dp[i][j] << endl << endl;
//    }
    int res = 0;
    forn(i, 1, n) res = add(res, dp[m][i]);
    cout << res << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int TC = 1;

    if(fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }


    while(TC--)
    {
        solve();
        cout << endl;
    }

    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1360 ms 6592 KB Output is correct
2 Correct 1353 ms 6816 KB Output is correct
3 Correct 1403 ms 6864 KB Output is correct
4 Correct 1356 ms 6532 KB Output is correct
5 Correct 1357 ms 6520 KB Output is correct
6 Correct 1313 ms 6964 KB Output is correct
7 Correct 1313 ms 6736 KB Output is correct
8 Correct 1353 ms 7064 KB Output is correct
9 Correct 1317 ms 6768 KB Output is correct
10 Correct 1334 ms 6816 KB Output is correct
11 Correct 1317 ms 6540 KB Output is correct
12 Correct 1325 ms 6640 KB Output is correct
13 Correct 1322 ms 6640 KB Output is correct
14 Correct 1318 ms 6784 KB Output is correct
15 Correct 1313 ms 6628 KB Output is correct
16 Correct 243 ms 3780 KB Output is correct
17 Correct 258 ms 3452 KB Output is correct
18 Correct 249 ms 3348 KB Output is correct
19 Correct 261 ms 3432 KB Output is correct
20 Correct 251 ms 3408 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1360 ms 6592 KB Output is correct
2 Correct 1353 ms 6816 KB Output is correct
3 Correct 1403 ms 6864 KB Output is correct
4 Correct 1356 ms 6532 KB Output is correct
5 Correct 1357 ms 6520 KB Output is correct
6 Correct 1313 ms 6964 KB Output is correct
7 Correct 1313 ms 6736 KB Output is correct
8 Correct 1353 ms 7064 KB Output is correct
9 Correct 1317 ms 6768 KB Output is correct
10 Correct 1334 ms 6816 KB Output is correct
11 Correct 1317 ms 6540 KB Output is correct
12 Correct 1325 ms 6640 KB Output is correct
13 Correct 1322 ms 6640 KB Output is correct
14 Correct 1318 ms 6784 KB Output is correct
15 Correct 1313 ms 6628 KB Output is correct
16 Correct 243 ms 3780 KB Output is correct
17 Correct 258 ms 3452 KB Output is correct
18 Correct 249 ms 3348 KB Output is correct
19 Correct 261 ms 3432 KB Output is correct
20 Correct 251 ms 3408 KB Output is correct
21 Incorrect 1286 ms 6540 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 1624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1360 ms 6592 KB Output is correct
2 Correct 1353 ms 6816 KB Output is correct
3 Correct 1403 ms 6864 KB Output is correct
4 Correct 1356 ms 6532 KB Output is correct
5 Correct 1357 ms 6520 KB Output is correct
6 Correct 1313 ms 6964 KB Output is correct
7 Correct 1313 ms 6736 KB Output is correct
8 Correct 1353 ms 7064 KB Output is correct
9 Correct 1317 ms 6768 KB Output is correct
10 Correct 1334 ms 6816 KB Output is correct
11 Correct 1317 ms 6540 KB Output is correct
12 Correct 1325 ms 6640 KB Output is correct
13 Correct 1322 ms 6640 KB Output is correct
14 Correct 1318 ms 6784 KB Output is correct
15 Correct 1313 ms 6628 KB Output is correct
16 Correct 243 ms 3780 KB Output is correct
17 Correct 258 ms 3452 KB Output is correct
18 Correct 249 ms 3348 KB Output is correct
19 Correct 261 ms 3432 KB Output is correct
20 Correct 251 ms 3408 KB Output is correct
21 Incorrect 1286 ms 6540 KB Output isn't correct
22 Halted 0 ms 0 KB -