oj.uz

Submission #480663

# Submission time Handle Problem Language Result Execution time Memory
480663 2021-10-17T15:10:50 Z TAMREF Boat (APIO16_boat) C++17
36 / 100
 2000 ms 8268 KB 
#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define bi_pc __builtin_popcount
#define bi_pcll __builtin_popcountll
#define bi_tz __builtin_ctz
#define bi_tzll __builtin_ctzll
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#ifdef TAMREF
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 42
#endif
using namespace std;
using ll = long long; using lf = long double; 
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pll = pair<ll,ll>; using pff = pair<lf,lf>;
using ti = tuple<int,int,int>;
using base = complex<double>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;

ll inv[505] = {0, 1};

int n;
vector<int> cmp;
int a[505], b[505];

ll a_Ijk[2][1005][505]; // i' < i, j' = j, k' = k
ll b_ij[2][1005]; //i' < i, j' < j, k' arb
ll ans;

int main(){
    fio;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        ++b[i];
        cmp.pp(a[i]); cmp.pp(b[i]);
    }
    for(int i = 2; i <= n; i++) {
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        debug("inv[%d] = %lld\n", i, inv[i]);
    }
    sort(all(cmp)); cmp.erase(unique(all(cmp)), cmp.end());
    int d = szz(cmp);
    for(int i = 1; i <= n; i++) {
        a[i] = lb(all(cmp), a[i]) - cmp.begin() + 1;
        b[i] = lb(all(cmp), b[i]) - cmp.begin() + 1;
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j < d; j++) {
            b_ij[i & 1][j] = (b_ij[~i & 1][j] + b_ij[i & 1][j-1] + mod - b_ij[~i & 1][j-1]) % mod;
            for(int k = 1; k <= n; k++) {
                a_Ijk[i & 1][j][k] = a_Ijk[~i & 1][j][k];
                ll dp = 0;
                if(a[i] <= j && j < b[i]) {
                    ll len = cmp[j] - cmp[j-1];
                    if(k == 1) {
                        dp = (1 + b_ij[~i & 1][j-1]) * len % mod;
                    }else{
                        dp = a_Ijk[~i & 1][j][k-1] * (len - k + 1) % mod * inv[k] % mod;
                    }
                }
                (a_Ijk[i & 1][j][k] += dp) %= mod;
                (b_ij[i & 1][j] += dp) %= mod;
                (ans += dp) %= mod;
            }
        }
    }
    cout << ans << endl;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
boat.cpp:56:9: note: in expansion of macro 'debug'
   56 |         debug("inv[%d] = %lld\n", i, inv[i]);
      |         ^~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1217 ms 8236 KB Output is correct
2 Correct 1253 ms 8236 KB Output is correct
3 Correct 1240 ms 8236 KB Output is correct
4 Correct 1230 ms 8232 KB Output is correct
5 Correct 1309 ms 8236 KB Output is correct
6 Correct 1209 ms 8268 KB Output is correct
7 Correct 1237 ms 8236 KB Output is correct
8 Correct 1209 ms 8244 KB Output is correct
9 Correct 1269 ms 8232 KB Output is correct
10 Correct 1216 ms 8232 KB Output is correct
11 Correct 1219 ms 8236 KB Output is correct
12 Correct 1263 ms 8232 KB Output is correct
13 Correct 1233 ms 8232 KB Output is correct
14 Correct 1225 ms 8232 KB Output is correct
15 Correct 1225 ms 8140 KB Output is correct
16 Correct 217 ms 1740 KB Output is correct
17 Correct 234 ms 1740 KB Output is correct
18 Correct 219 ms 1784 KB Output is correct
19 Correct 233 ms 1740 KB Output is correct
20 Correct 224 ms 1740 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1217 ms 8236 KB Output is correct
2 Correct 1253 ms 8236 KB Output is correct
3 Correct 1240 ms 8236 KB Output is correct
4 Correct 1230 ms 8232 KB Output is correct
5 Correct 1309 ms 8236 KB Output is correct
6 Correct 1209 ms 8268 KB Output is correct
7 Correct 1237 ms 8236 KB Output is correct
8 Correct 1209 ms 8244 KB Output is correct
9 Correct 1269 ms 8232 KB Output is correct
10 Correct 1216 ms 8232 KB Output is correct
11 Correct 1219 ms 8236 KB Output is correct
12 Correct 1263 ms 8232 KB Output is correct
13 Correct 1233 ms 8232 KB Output is correct
14 Correct 1225 ms 8232 KB Output is correct
15 Correct 1225 ms 8140 KB Output is correct
16 Correct 217 ms 1740 KB Output is correct
17 Correct 234 ms 1740 KB Output is correct
18 Correct 219 ms 1784 KB Output is correct
19 Correct 233 ms 1740 KB Output is correct
20 Correct 224 ms 1740 KB Output is correct
21 Correct 1783 ms 7548 KB Output is correct
22 Correct 1770 ms 7640 KB Output is correct
23 Correct 1690 ms 7508 KB Output is correct
24 Correct 1742 ms 7492 KB Output is correct
25 Correct 1774 ms 7500 KB Output is correct
26 Correct 1973 ms 7356 KB Output is correct
27 Execution timed out 2031 ms 7408 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1920 KB Output is correct
2 Correct 19 ms 1924 KB Output is correct
3 Correct 17 ms 1868 KB Output is correct
4 Correct 17 ms 1900 KB Output is correct
5 Correct 17 ms 1920 KB Output is correct
6 Correct 23 ms 1868 KB Output is correct
7 Correct 21 ms 1920 KB Output is correct
8 Correct 20 ms 1868 KB Output is correct
9 Correct 20 ms 1868 KB Output is correct
10 Correct 19 ms 1920 KB Output is correct
11 Correct 18 ms 1920 KB Output is correct
12 Correct 16 ms 1920 KB Output is correct
13 Correct 16 ms 1920 KB Output is correct
14 Correct 16 ms 1916 KB Output is correct
15 Correct 17 ms 1916 KB Output is correct
16 Correct 10 ms 1248 KB Output is correct
17 Correct 10 ms 1228 KB Output is correct
18 Correct 10 ms 1228 KB Output is correct
19 Correct 10 ms 1244 KB Output is correct
20 Correct 10 ms 1100 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1217 ms 8236 KB Output is correct
2 Correct 1253 ms 8236 KB Output is correct
3 Correct 1240 ms 8236 KB Output is correct
4 Correct 1230 ms 8232 KB Output is correct
5 Correct 1309 ms 8236 KB Output is correct
6 Correct 1209 ms 8268 KB Output is correct
7 Correct 1237 ms 8236 KB Output is correct
8 Correct 1209 ms 8244 KB Output is correct
9 Correct 1269 ms 8232 KB Output is correct
10 Correct 1216 ms 8232 KB Output is correct
11 Correct 1219 ms 8236 KB Output is correct
12 Correct 1263 ms 8232 KB Output is correct
13 Correct 1233 ms 8232 KB Output is correct
14 Correct 1225 ms 8232 KB Output is correct
15 Correct 1225 ms 8140 KB Output is correct
16 Correct 217 ms 1740 KB Output is correct
17 Correct 234 ms 1740 KB Output is correct
18 Correct 219 ms 1784 KB Output is correct
19 Correct 233 ms 1740 KB Output is correct
20 Correct 224 ms 1740 KB Output is correct
21 Correct 1783 ms 7548 KB Output is correct
22 Correct 1770 ms 7640 KB Output is correct
23 Correct 1690 ms 7508 KB Output is correct
24 Correct 1742 ms 7492 KB Output is correct
25 Correct 1774 ms 7500 KB Output is correct
26 Correct 1973 ms 7356 KB Output is correct
27 Execution timed out 2031 ms 7408 KB Time limit exceeded
28 Halted 0 ms 0 KB -