oj.uz

Submission #1015085

# Submission time Handle Problem Language Result Execution time Memory
1015085 2024-07-06T04:57:59 Z vjudge1 Boat (APIO16_boat) C++17
0 / 100
 252 ms 524288 KB 
#include<bits/stdc++.h>

using namespace std;

const int mod = 1'000'000'007;

int main()
{
  int n;
  cin >> n;
  int a[1 + n], b[1 + n]; // [a[i], a[i] + b[i])
  a[0] = 0, b[0] = 1;
  for(int i = 1; i <= n; i++)
    {
      cin >> a[i] >> b[i];
      b[i] = b[i] - a[i] + 1;
    }

  

  vector<vector<int> > dp(1 + n);
  dp[0].push_back(1);

  for(int i = 1; i <= n; i++)
    {
      dp[i].resize(b[i]);
      for(int j = 0; j < b[i]; j++)
	{
	  int x = a[i] + j;
	  for(int k = 0; k < i; k++)
	    {
	      int len = min(b[k], max(0, x - a[k]));
	      if(len > 0) dp[i][j] += dp[k][len - 1];
	    }
	}

      for(int j = 1; j < b[i]; j++)
	dp[i][j] += dp[i][j - 1], dp[i][j] %= mod;
    }
  int ans = 0;
  for(int i = 1; i <= n; i ++)
    ans += dp[i].back(), ans %= mod;
  cout << ans << endl;
  return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 252 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

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