Submission #30778

#	Time	Username	Problem	Language	Result	Execution time	Memory
30778		kavun	Boat (APIO16_boat)	C++14	0 / 100	0 ms	1844 KiB

boat

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 501;
int dp[maxn][1000001], a[1000001], b[1000001], ans;
int n;

int f(int i, int j)
{
  if(j > b[i] - a[i])
    return 0;
  if(dp[i][j])
    return dp[i][j];
  if(i == 0 && j <= b[i] - a[i])
    return 1;

  for(int k = 0; k < i; k++)
    for(int l = 0;l < a[i]+j-a[k]; l++)
      dp[i][j] += f(k,l);
  return ++dp[i][j];
}

int main()
{
  cin >> n;
  for(int i = 0; i < n; i++)
    cin >> a[i] >> b[i];
  for(int i = 0; i < n; i++)
    for(int j = 0; j <= b[i] - a[i]; j++)
      ans = (ans + f(i,j)) % mod;
  cout << ans << endl;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42