Submission #1313691

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313691		thuhienne	Boat (APIO16_boat)	C++20	9 / 100	160 ms	4308 KiB

boat

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define re exit(0);

const int mod = 1e9 + 7;

int n,a[509],b[509];

vector <int> X;

int dp[509][1009],pref[509][1009];

int cnt;
pair <int,int> halfseg[1009];

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);

	cin >> n;
	for (int i = 1;i <= n;i++) {
		cin >> a[i] >> b[i];
		X.push_back(a[i] - 1);
		X.push_back(b[i]);
	}
	
	sort(X.begin(),X.end());
	
	X.resize(unique(X.begin(),X.end()) - X.begin());
	for (int i = 0;i < (int)X.size() - 1;i++) {
		halfseg[++cnt] = {X[i],X[i + 1]};
	}
	
//	for (int i = 1;i <= cnt;i++) cout << halfseg[i].first << " " << halfseg[i].second << '\n';
//	cout << '\n';
	
	int res = 0;
	
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= cnt;j++) {
			
			if (a[i] <= halfseg[j].first + 1 && halfseg[j].second <= b[i]) {
				dp[i][j] = halfseg[j].second - halfseg[j].first;
				
				for (int k = i - 1;k >= 1;k--) {
					dp[i][j] = (dp[i][j] + 1ll * pref[k][j - 1] * (halfseg[j].second - halfseg[j].first)) % mod;
				}
			
//				cout << i << " " << halfseg[j].first + 1 << " " << halfseg[j].second << " " << dp[i][j] << '\n';
			
			}
			
			
			pref[i][j] = (pref[i][j - 1] + dp[i][j]) % mod;
			
			res = (res + dp[i][j]) % mod;
		}
	}
	
	cout << res;

}

/*
Aiming:
                                                           ==
                                                         +++++***
                                                        +:::::-=*
                                                         ------=
         ==========           ==================         --:--==              ============--
         ==========           ==-------=--:=--====       ---==++           ===========--====-=
        ==--========          ==--=================      =:::-=+          ==============----====
        ==:-=========         ===:===       =======      =::--=+         ========        ==--====
       ==--==========         ==-:===        =======     -:::-:=        =======           =======
      ==--:==  =======        ==--===        =======     =-:::-=        =======            =======
      =-.-===   =======       ==-====       =======     *:::----*       =======            =======
     ==--:==    =======       ==-==================     +-:::::-+       ======             =======
    ==-:-===     =======      ==--================     *=-:::::-=       =======            =======
    ==---===============      ==--=============        +--::---==*      ====--=            =======
   ===--=================     ==:-===                  =:-::::--=+      ====-===          =======
   ==.-===================    ==--===                  =::::::---+       ====---==      =========
  ==---==          =======    =======                 +-:---=====+        ==-===--==============
 =======            =======   =======                 =-:::::::--=+         =--=-=============
========             =======  =======                 =--::::::--=+           =============
                                                   ***++++++++++*****
*/

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