Submission #1307069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307069		namhh	Boat (APIO16_boat)	C++20	100 / 100	613 ms	8488 KiB

boat

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e3+5;
const int MOD = 1e9+7;
int n,dp[N][N],pre[N][N],inv[N];
pii a[N];
vector<int>loj;
int modpow(int a, int b){
	int res = 1;
	while(b){
		if(b & 1) res = (res*a) % MOD;
		a = (a*a) % MOD;
		b >>= 1;
	}
	return res;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i].fi >> a[i].se;
		a[i].se++;
		loj.push_back(a[i].fi);
		loj.push_back(a[i].se);
	}
	sort(loj.begin(),loj.end());
	loj.erase((loj.begin(),loj.end()),loj.end());
	int lim = loj.size()-1;
	for(int i = 0; i <= lim; i++) pre[0][i] = 1;
	for(int i = 1; i <= n; i++) inv[i] = modpow(i,MOD-2);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= lim; j++){
			int cur = 1;
			int val = loj[j]-loj[j-1];
			int num = 0;
			for(int k = i; k >= 1; k--){
				if(a[k].fi <= loj[j-1] && a[k].se >= loj[j]){
					cur = cur*(val+num) % MOD*inv[num+1] % MOD;
					num++;
					dp[i][j] = (dp[i][j]+pre[k-1][j-1]*cur) % MOD;
				}
			}
		}
		pre[i][0] = 1;
		for(int j = 1; j <= lim; j++) pre[i][j] = (pre[i][j-1]+dp[i][j]) % MOD;
	}
	pre[n][lim] = (pre[n][lim]-1) % MOD+MOD;
	cout << pre[n][lim] % MOD;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:32:29: warning: ignoring return value of 'constexpr std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::begin() [with _Tp = long long int; _Alloc = std::allocator<long long int>; iterator = std::vector<long long int>::iterator]', declared with attribute 'nodiscard' [-Wunused-result]
   32 |         loj.erase((loj.begin(),loj.end()),loj.end());
      |                    ~~~~~~~~~^~
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53,
                 from boat.cpp:1:
/usr/include/c++/13/bits/stl_vector.h:873:7: note: declared here
  873 |       begin() _GLIBCXX_NOEXCEPT
      |       ^~~~~

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