oj.uz

Submission #699560

# Submission time Handle Problem Language Result Execution time Memory
699560 2023-02-17T12:00:11 Z Abrar_Al_Samit Boat (APIO16_boat) C++17
36 / 100
 2000 ms 3576 KB 
#include<bits/stdc++.h>
using namespace std;

const int nax = 503;
const int mod = 1e9 + 7;

vector<int>ind[nax*2];
int a[nax], b[nax];
int n, m;
int dp[nax*2][nax];
int inv[nax];
vector<int>imp;

int add(int a, int b) {
  a += b;
  if(a>=mod) a -= mod;
  return a;
}
int mul(int a, int b) {
  return (a * 1LL * b) % mod;
}
int quickpow(int a, int b) {
  int ret = 1;
  while(b) {
    if(b&1) ret = mul(ret, a);
    a = mul(a, a);
    b >>= 1;
  }
  return ret;
}

int get(int x) {
  int &ret = inv[x];
  if(ret==-1) {
    ret = quickpow(x, mod-2);
  }
  return ret;
}
map<pair<int,int>,int>table;
int C(int n, int r) {
  int& ret = table[{n, r}];
  if(ret==0) {
    ret = 1;
    for(int i=n-r+1; i<=n; ++i) {
      ret = mul(ret, i);
    }
    for(int i=1; i<=r; ++i) {
      ret = mul(ret, get(i));
    }
  }
  return ret;
}
int solve(int i, int prv) {
  if(i==m-1) return prv>0;
  int &ret = dp[i][prv];
  if(ret!=-1) return ret;
  ret = 0;

  ret = solve(i+1, prv);
  int len = imp[i+1]-imp[i];

  for(int mx=0, cur_op=0; mx<ind[i].size(); ++mx) {
    if(ind[i][mx]<=prv) continue;

    int cur = solve(i+1, ind[i][mx]);
    for(int take=0; take<=min(cur_op, len-1); ++take) {
      ret = add(ret, mul(cur, mul(C(cur_op, take), C(len, take+1))));
    }
    cur_op++;
  }
  return ret;
}
void PlayGround() {
  cin>>n;
  set<int>pts;
  for(int i=1; i<=n; ++i) {
    cin>>a[i]>>b[i];
    pts.insert(a[i]);
    pts.insert(b[i]+1);
  }

  for(int x : pts) {
    imp.push_back(x);
  } 
  m = imp.size();
  for(int i=0; i<m; ++i) {
    for(int j=1; j<=n; ++j) {
      if(imp[i]>=a[j] && imp[i]<=b[j]) {
        ind[i].push_back(j);
      }
    }
  }
  memset(inv, -1, sizeof inv);
  memset(dp, -1, sizeof dp);
  cout<<solve(0, 0)<<'\n';


  // cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Compilation message

boat.cpp: In function 'int solve(int, int)':
boat.cpp:62:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int mx=0, cur_op=0; mx<ind[i].size(); ++mx) {
      |                           ~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2516 KB Output is correct
2 Correct 9 ms 2516 KB Output is correct
3 Correct 8 ms 2520 KB Output is correct
4 Correct 8 ms 2516 KB Output is correct
5 Correct 9 ms 2520 KB Output is correct
6 Correct 8 ms 2516 KB Output is correct
7 Correct 10 ms 2524 KB Output is correct
8 Correct 9 ms 2524 KB Output is correct
9 Correct 11 ms 2436 KB Output is correct
10 Correct 8 ms 2516 KB Output is correct
11 Correct 9 ms 2516 KB Output is correct
12 Correct 8 ms 2516 KB Output is correct
13 Correct 7 ms 2464 KB Output is correct
14 Correct 7 ms 2520 KB Output is correct
15 Correct 13 ms 2644 KB Output is correct
16 Correct 5 ms 2368 KB Output is correct
17 Correct 5 ms 2260 KB Output is correct
18 Correct 4 ms 2260 KB Output is correct
19 Correct 5 ms 2260 KB Output is correct
20 Correct 5 ms 2260 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2516 KB Output is correct
2 Correct 9 ms 2516 KB Output is correct
3 Correct 8 ms 2520 KB Output is correct
4 Correct 8 ms 2516 KB Output is correct
5 Correct 9 ms 2520 KB Output is correct
6 Correct 8 ms 2516 KB Output is correct
7 Correct 10 ms 2524 KB Output is correct
8 Correct 9 ms 2524 KB Output is correct
9 Correct 11 ms 2436 KB Output is correct
10 Correct 8 ms 2516 KB Output is correct
11 Correct 9 ms 2516 KB Output is correct
12 Correct 8 ms 2516 KB Output is correct
13 Correct 7 ms 2464 KB Output is correct
14 Correct 7 ms 2520 KB Output is correct
15 Correct 13 ms 2644 KB Output is correct
16 Correct 5 ms 2368 KB Output is correct
17 Correct 5 ms 2260 KB Output is correct
18 Correct 4 ms 2260 KB Output is correct
19 Correct 5 ms 2260 KB Output is correct
20 Correct 5 ms 2260 KB Output is correct
21 Execution timed out 2084 ms 3576 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 2832 KB Output is correct
2 Correct 218 ms 2676 KB Output is correct
3 Correct 288 ms 2772 KB Output is correct
4 Correct 314 ms 2848 KB Output is correct
5 Correct 411 ms 2908 KB Output is correct
6 Correct 1220 ms 3348 KB Output is correct
7 Correct 1155 ms 3416 KB Output is correct
8 Correct 1159 ms 3380 KB Output is correct
9 Correct 1253 ms 3216 KB Output is correct
10 Correct 1199 ms 3232 KB Output is correct
11 Correct 440 ms 2916 KB Output is correct
12 Correct 277 ms 2840 KB Output is correct
13 Correct 320 ms 2776 KB Output is correct
14 Correct 331 ms 2904 KB Output is correct
15 Correct 420 ms 2868 KB Output is correct
16 Correct 145 ms 2616 KB Output is correct
17 Correct 110 ms 2600 KB Output is correct
18 Correct 136 ms 2612 KB Output is correct
19 Correct 102 ms 2580 KB Output is correct
20 Correct 158 ms 2556 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2516 KB Output is correct
2 Correct 9 ms 2516 KB Output is correct
3 Correct 8 ms 2520 KB Output is correct
4 Correct 8 ms 2516 KB Output is correct
5 Correct 9 ms 2520 KB Output is correct
6 Correct 8 ms 2516 KB Output is correct
7 Correct 10 ms 2524 KB Output is correct
8 Correct 9 ms 2524 KB Output is correct
9 Correct 11 ms 2436 KB Output is correct
10 Correct 8 ms 2516 KB Output is correct
11 Correct 9 ms 2516 KB Output is correct
12 Correct 8 ms 2516 KB Output is correct
13 Correct 7 ms 2464 KB Output is correct
14 Correct 7 ms 2520 KB Output is correct
15 Correct 13 ms 2644 KB Output is correct
16 Correct 5 ms 2368 KB Output is correct
17 Correct 5 ms 2260 KB Output is correct
18 Correct 4 ms 2260 KB Output is correct
19 Correct 5 ms 2260 KB Output is correct
20 Correct 5 ms 2260 KB Output is correct
21 Execution timed out 2084 ms 3576 KB Time limit exceeded
22 Halted 0 ms 0 KB -