Submission #401956

#	Time	Username	Problem	Language	Result	Execution time	Memory
401956		Maqsut_03	Boat (APIO16_boat)	C++14	100 / 100	1463 ms	4296 KiB

boat

#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

vector<int> aux;
array<int, 2> v[505];
ll dp[1005][505], inv[505];

int main()
{
    int n, i, j, e;
    scanf("%d" ,&n);
    aux = {-1};
    inv[1] = 1;
    for(i=2; i<=n; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
   
    for(i=1;i<=n;i++)
	{
        scanf("%d%d",&v[i][0],&v[i][1]);
        ++v[i][1];
        aux.push_back(v[i][0]);
        aux.push_back(v[i][1]);
    }
    
	sort(aux.begin(),aux.end());
  //  aux.resize(unique(aux.begin(),aux.end())-aux.begin());
    int m=aux.size();
    for(i=0;i<m;i++) dp[i][0]=1;
    
	for(i=1; i<=n; i++)
	{
        for(j=m-1; j>=1; j--)
            if (v[i][0]<=aux[j-1] && aux[j]<=v[i][1])
			{
                int cnt=aux[j]-aux[j-1];
                for(e=min(cnt,i);e>=1;e--)
                    dp[j][e]=(dp[j][e]+dp[j][e-1]*(cnt-e+1)%mod*inv[e])%mod;
            }
        for(j=1;j<=m;j++)
		{
            dp[j][0]=0;
            for(e=0;e<=n;e++)
                dp[j][0]=(dp[j][0]+dp[j-1][e])%mod;
        }
    }
    printf("%lld\n", (dp[m][0] + mod - 1) % mod);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d" ,&n);
      |     ~~~~~^~~~~~~~~~
boat.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         scanf("%d%d",&v[i][0],&v[i][1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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