Submission #1239270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239270		Joon_Yorigami	Boat (APIO16_boat)	C++17	100 / 100	317 ms	13128 KiB

boat

/*
                                                                   .:-=++***#***+=:.
                                                       .:-==+**##**%########***#####*=:.
                                                   .-+#%%#*****############**#******#####+=:
                                                .-*%#####********###########*********#######*+-:
                                              :+#######**********########*****+********##########+-.
                                            :+##########**###******##********************###########+:
                                          :+##########*****#*******###**********************###***####*:
                                        .=###########***###*******#***************************#****#####*:
                                       :*#################******************************************######=
                                      -###################***************+****************************#####*:
                                    .=###################******************************************#****#####+.
                                   :*###################*******************************+************#*****#####:
                                  =#############**######*****#*******************++***++++++***************#####=
                                .*###########******####*****#************+++*+**+++***++++++++***#**********#####+
                               -############********###*****%*+****+++++++++++++++++***++++++++***#*****#****#####*
                              =############********###+++++##++++++++++++++++*++++++****++++******##*+++*#****#####*.
                            .+#*##########*********###+++++%*++==++++++++++++*+++++*#************#*##*+++##****#####*.
                           .*#=-##########********###*++++*%*+++++++++++++*****+******#***********#*##*+++####*######*.
               .:-:       .*#: *#########*********###+++++##****++*******************#*#**********##*#*****####*#%###%*.
           .--:++=+.     .**.  ##########********##*#++***%#****+*************=#*****#*#**********##*##*##*####**#%###%*:
           :++=====     .**.  -###########******##*##+****%#*****#************-********#**********#***%####*###***#%######=:
            .-=++=      =*.   +############****###*##*****%#*****%####*####**#:=#***#**#**********#=##*###**####***#%########+:
                .      .#.   .####################*##*****%#####*%#****##****#.:#***#*#**********#%:##*+##***%###***############+:
                       --    -###################**#*****####****##****##*****..#*****#**********#*.*#+ +##**#####***##############+-.
         -=+++-.       =     +###################**#*****###**********#*#***#: .***#*#***********#:.*#- :**#*######***#######%%%####%%#=:
       .++====++       =     ####################**##*****###***#+****#=#****  .+*###************+  ##   +***######****##########+--+#%%%%+:
  .---:=+======+:      +.    ##################%#***#*****####****#**#+-####.  .+###***##*******#  .#:   :***########***##%%%####%#=. .:=*%%
 ---==++=======+=      -=   .%#################%****#*****######-#*##*.=%#*.    +=---:::.......:   =:     =**#########***#%%%%%%%%%%%=.   .-
 :-:===========+=      .#.  :%################%%****#*****#####= :-+***#*=.                               .*#########%%#**#*=%%%%%%%%%%=.
  .---=========+=       :*. -#################%%****#*****%#+-.-*#%%%@###*=                                +##########%%%***:+-#%%%#####*:
    .:=++++====+-        =*.=###%############%@%****#*****#. =###%%%@@@+                                   ###########%%%%#*#:  -*########=
        ..:::::-.         +*+###%####%######%%+******#****#=##= -@@@@@@@+                                 =*###########%%%%##+    :*#######+
                           =%##+%####%######%+.******#*****%%#-:+@@@@%-=*                                 +..###########%##%%%*.    -#######
                            %##=#####%###%%#%:=******#*****%*.**##*+=:  .                   -+**####*=:  -  .=###############%%*:    .+#####
                           .%###%########%%%%:.#*****##*****= .+:      .                   :-::.:--=++-  :  .-*##################+:    :####
                           :##.*###########%@# #************+   .:.-==--                                .    +**###+*##############*:   .*##
                           -%- ############%@@-#*###*#=##***#.                                          :.  =*++*#**++*##############*-  .##
                           =#  ############@@@######*#:###*##=                                          :..+*++++***+++++*##############=.+#
                           +:  ###########%@%%%%######.=######                                         .=+#+++++++***+++++****##############
                          .+   *##########%%%%%%######::######=                                        =+++#*+++++++*#+++++******###########
                          +:   =%#%######%%%##%@######:-+######.              .:------==              :*++++**+++++++*#*+++++********#######
                         -*    :%%%%#####%%%##%%%#####***######*             -=--------=:            -*+++++++*++++++++*#**+++*=:=******+==*
                        .*+     +%%%%###%%####%%%#####**+#######=            -........:=:          -++++++++++*#**##***+******++- .-******=.
                        -*=      *%%%%##%%%%%%%#%#####**++#######.           :.........-        .=#%%%######%##########%#+*******.  .-++++*+
                        -*+     .*%%%%#%%#######%#####*++++######*:           .........      :=#%@@%%%%%%#################*++*****=.  .-++++
                        :**.   :###%%%#%%########%####*++++*#######=-:..                  -+#%%%###########################++++****#=.  .-++
                         -*+  .######%%%%#########%###@@@%%%%######+...:----:.         :*%################################%*+++++*+###-   .+
                          :*+.=########%%%%###########%%%%%%%%######-........:------::.+%%%%%###############%#############%*+++++*.:*##+.  .
                            -+####****##%%%%%%%%###%########%%@%#####:.......:::::::...=@@%%%@###############%############%*+++++*.  =##+
                             +#*##*****####%%%%##%%%%#########%@%#####:.....-:....:..::=*=++++############################%#*+++++    -##.
                            =%**********#######%%###############%*#####=...=.        .  :-=-: .###############%#******####%#####+=     +*
                            *#************#############%%#######**+*%####-.-                .-:=##############%*********##%#######=:  .+.
                            *#****************##**######%%%###*:   ::*#####:     -::            .-+####%%%####%*********#%##########*-:
                            =#***********************######%*-        .--:=:.   =. :--:             .-=*###%###*********#######*#######+-
                            .#**************************###=             .:.  ::...   .=.               +***#%##*******#########***#######+:
                             =##**************************:      :-:--.  .. .+.....     +               =******#%#####%##########***#####**#
                              ####**********************+.    . :#########+-=:....      -:              +***********##%%#***######****##****
                              .#%####******************-        *##########*:....... ...:.              #**************##*********###*##****
                               :#%@%%%###*************          =#*******####+....... :-.              *#***************%************#%#****
                              .#**###%%%%%######****#.           =#***********#=....:-.              :*#****************##*************####*
                              *#**#****#####%%%%#####             =#*************+=:       .=-::..:-*#*****************##*****************##
                             -#***#*******######%%%%=               :=*#**********:    ...  ##*##%##*******************#********************
                            .%*****#*********######%.                    ....:-=*-  :++:   =#****##%####*************###********************
:.                          +#*****#**********####%+                            ..-*#***#+=##*******##%%###********####*********************
 .:-:.                     .%#*****#**********#%%%*                  :=+**##########******###********#%%%%%%##****###***********************
     --                    =%#******#*********@#%%-.               :#%%%%%%%%%%%%%%###*****###*****#%%##%%%#%@#####*************************
=-.   .=.                  ##*******#********#%#**###*+=-:.:     -######%##%###%####%%%%%##########%####%%%%##%*************####************
====   .=                 :%#*******#********%%***************++#%%#%#######%###%#######%%%%%%%########%%%%####%#************####***********
 ====   -:                *%#*******#********@#********************#%#######%###%###########%%%%%#####%%%#######%%#**********#####**********
 :+=+.   =               .%###*******#******#%#*******************#%#############%##############%%%##%######***####%%#*******######*********
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<long long>;
ll binpow(ll a, ll b, ll m)
{
  a %= m;
  ll res = 1;
  while (b > 0)
  {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res%m;
}

ll modinv(ll x,ll m)
{
  return binpow(x,m-2,m)%m;
}

constexpr ll max_n=600;
constexpr ll mod=1000000007;

ll comb[2*max_n+1][2*max_n+1];
ll dp[2*max_n+1][2*max_n+1];
ll arr[max_n+1];
ll barr[max_n+1];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;
  cin >> n;
  vll coords;
  set<ll> seen;
  for(int i=0;i<n;i++)
  {
    cin >> arr[i] >> barr[i];
    arr[i]-=1;
    if(seen.find(arr[i])==seen.end())
    {
      coords.push_back(arr[i]);
      seen.insert(arr[i]);
    }
    if(seen.find(barr[i])==seen.end())
    {
      coords.push_back(barr[i]);
      seen.insert(barr[i]);
    }
  }
  sort(coords.begin(),coords.end());
  ll m=coords.size();
  for(int i=1;i<m;i++)
  {
    ll gap=coords[i]-coords[i-1];
    comb[i][1]=gap;
    for(int k=2;k<=n;k++)
    {
      comb[i][k]=comb[i][k-1]*(gap+k-1)%mod*modinv(k,mod)%mod;
    }
  }
  for(int i=0;i<m;i++)
  {
    dp[0][i]=1;
  }
  for(int i=1;i<=n;i++)
  {
		dp[i][0]=1;
		for(int j=1;j<m;j++) 
    {
      ll n2=0;
			dp[i][j]=dp[i][j-1];
			for(int k=i;k;k--)
      {
				if(coords[j]>arr[k-1]&&coords[j]<=barr[k-1])
        {
					n2+=1;
					dp[i][j]+=dp[k-1][j-1]*comb[j][n2]%mod;
				}
			}
			dp[i][j]%=mod;
		}
	}
	cout << (dp[n][m-1]-1+mod)%mod << endl;;
}

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