Submission #253266

#	Time	Username	Problem	Language	Result	Execution time	Memory
253266		davooddkareshki	Boat (APIO16_boat)	C++17	100 / 100	1126 ms	12456 KiB

boat

#include<bits/stdc++.h>

using namespace std; 

typedef long long ll;
typedef long double ld;

#define F first 
#define S second 
#define pii pair<int,int>
#define mpr make_pair

const int maxn = 1010;
const ll inf = 1e18+10;
const int mod = 1e9+7;
const int N = 2e7+10;

int n;
int dp[maxn][maxn], sum[maxn][maxn], C[maxn][maxn], C2[maxn][maxn], a[maxn], b[maxn], fac[maxn], repo[maxn];
vector<int> ve;

int pw(int a, int b)
{
   if(b == 0) return 1;
   int x = pw(a,b/2); x = (x * 1ll * x) % mod;
   if(b&1) x = (x * 1ll * a) % mod;
   return x;
}

signed main()
{
   //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

   scanf("%d", &n);
   fac[0] = 1; repo[0] = 1;
   for(int i = 1; i <= n; i++) 
   {
      fac[i] = (fac[i-1] * 1ll * i) % mod;
      repo[i] = pw(fac[i],mod-2);
      
      scanf("%d%d", &a[i], &b[i]);
      ve.push_back(a[i]);
      ve.push_back(b[i]);
   }
   ve.push_back(0);
   sort(ve.begin(), ve.end());
   ve.resize(unique(ve.begin(), ve.end()) - ve.begin());
   int k = ve.size();

   for(int j = 0; j < k; j++)
      for(int x = 0; x <= n; x++)
      {
         int T;
         if(j == 0) T = 1;
         else T = ve[j] - ve[j-1];
         if(x <= 2)
         {
            int up = 1, dow = 1;
            for(int y = 1; y <= min(x,T); y++)
            {
               up = (up * 1ll * (T-y+1)) % mod;   
               dow = (repo[y-1] * 1ll * repo[x-y]) % mod; 
               dow = (dow * 1ll * repo[y]) % mod;
               (C[j][x] += (((fac[x-1] * 1ll * up) % mod) * 1ll * dow) % mod) %= mod;
            }

            up = 1; dow = 1; T--;
            for(int y = 0; y <= min(x,T); y++)
            {
               if(y) up = (up * 1ll * (T-y+1)) % mod;   
               dow = (repo[y] * 1ll * repo[x-y]) % mod; 
               dow = (dow * 1ll * repo[y]) % mod;
               (C2[j][x] += (((fac[x] * 1ll * up) % mod) * 1ll * dow) % mod) %= mod;
            }
         }
         else 
         {
            int up = 1;
            for(int y = 1; y <= x; y++) 
               up = (up * 1ll * (y+T-1)) % mod;
            C[j][x] = C2[j][x] = (up * 1ll * repo[x]) % mod;
         }

         //cout<< T <<" "<< x <<" "<< C[j][x] <<" "<< C2[j][x] <<"\n";
      }

   int ANS = 0;
   for(int i = 0; i <= n; i++)
      for(int j = 0; j < k; j++)
      {
         if(i == 0)
         {
            sum[i][j] = 1;
            dp[i][0] = 1;
            continue;
         }

         if(j == 0)
         {
            dp[i][j] = 1;
            sum[i][j] = 1;
         }
         else 
         {
            int L = ve[j-1]+1, R = ve[j];
            bool X = 0; int nm = 0;
            for(int x = i-1; x >= 0; x--)
            {
               int l = max(L,a[x+1]), r = min(R,b[x+1]);

               nm++;
               if(l > r && x == i-1) break;
               if(l > r) nm--;
               if(l == r) 
               {
                  if(x == i-1) X = 1;
                  nm--;  
               }

               int val = (sum[x][j-1]-1); if(!x) val = 1;
               if(!X)
                  (dp[i][j] += (val * 1ll * C[j][nm]) % mod) %= mod;
               else 
                  (dp[i][j] += ((val * 1ll * C2[j][nm]) % mod)) %= mod;
            }

            sum[i][j] = (sum[i][j-1] + dp[i][j]) % mod;
            (ANS += dp[i][j]) %= mod;
         }
         //cout<< i <<" "<< j <<" "<< dp[i][j] <<"\n";   
      }
   
   printf("%d", ANS);
}



/*
3
1 2  
5 10 
100 100

3
1 2
2 3
3 4
*/

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:34:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &n);
    ~~~~~^~~~~~~~~~
boat.cpp:41:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d", &a[i], &b[i]);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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