oj.uz

Submission #943814

# Submission time Handle Problem Language Result Execution time Memory
943814 2024-03-12T01:32:12 Z Boycl07 Boat (APIO16_boat) C++17
27 / 100
 2000 ms 4536 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) 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]  : 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] = 1;
            forn(k, 1, n) comb[k] = 1ll * comb[k - 1] * (r - l + k - 1) % MOD * inv[k] % MOD;
            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]));
                }
            }
        }
    }
    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 'void solve()':
boat.cpp:96:26: warning: unused variable 'cur' [-Wunused-variable]
   96 |             int cnt = 0, cur = 1;
      |                          ^~~
boat.cpp: In function 'int main()':
boat.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2024 ms 4536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2024 ms 4536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3160 KB Output is correct
2 Correct 27 ms 3164 KB Output is correct
3 Correct 28 ms 3156 KB Output is correct
4 Correct 27 ms 3236 KB Output is correct
5 Correct 28 ms 3164 KB Output is correct
6 Correct 28 ms 3152 KB Output is correct
7 Correct 28 ms 3164 KB Output is correct
8 Correct 29 ms 3164 KB Output is correct
9 Correct 28 ms 3164 KB Output is correct
10 Correct 28 ms 3160 KB Output is correct
11 Correct 28 ms 3160 KB Output is correct
12 Correct 28 ms 3156 KB Output is correct
13 Correct 27 ms 3412 KB Output is correct
14 Correct 27 ms 3160 KB Output is correct
15 Correct 27 ms 3164 KB Output is correct
16 Correct 16 ms 2764 KB Output is correct
17 Correct 15 ms 2908 KB Output is correct
18 Correct 16 ms 2908 KB Output is correct
19 Correct 16 ms 2944 KB Output is correct
20 Correct 15 ms 2904 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2024 ms 4536 KB Time limit exceeded
2 Halted 0 ms 0 KB -