Submission #1015086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015086		vjudge1	Boat (APIO16_boat)	C++17	31 / 100	1110 ms	524288 KiB

boat

#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];
	      dp[i][j] %= mod;
	    }
	}

      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: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42