Submission #930249

#	Time	Username	Problem	Language	Result	Execution time	Memory
930249		8pete8	Boat (APIO16_boat)	C++17	9 / 100	172 ms	12636 KiB

boat

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<numeric> //gcd(a,b)
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset> 
#include<stack>
//#include "aliens.h"
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
//#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#define int int64_t
const int mxn=1000+10,minf=-1e18,mod=1e9+7,inf=1e18,lg=30;
int dp[mxn+10][mxn+10],ncr[mxn+10][mxn+10];
//knapsack
int32_t main(){
	fastio
	int n;cin>>n;
	vector<pii>v(n+1);
	vector<int>com;
	int m=inf;
	for(int i=1;i<=n;i++)cin>>v[i].f>>v[i].s;
	for(int i=1;i<=n;i++)com.pb(v[i].f),com.pb(v[i].s);
	ncr[0][0]=1;
	for(int i=1;i<=2*n;i++)for(int j=0;j<=2*n;j++){
		if(j)ncr[i][j]=(ncr[i-1][j]+ncr[i-1][j-1])%mod;
		else ncr[i][j]=ncr[i-1][j];
	}
	for(int i=1;i<=2*n;i++)for(int j=2;j<=2*n;j++)ncr[i][j]=(ncr[i][j]+ncr[i][j-1])%mod;//choose n,all r
	com.pb(minf);
	sort(all(com));
	com.erase(unique(all(com)),com.end());
	for(auto &i:v){
		i.f=lb(all(com),i.f)-com.begin();
		i.s=lb(all(com),i.s)-com.begin();
	}
	for(int i=0;i<=2*n;i++)dp[0][i]=1;
	for(int i=1;i<=n;i++){
		//dp pref i,j ->ith range choose in jth segment
		int sum=0;
		for(int j=v[i].f;j<=v[i].s;j++){
			int len,cnt=0;
			if(j==v[i].f){
				for(int back=i;back>=1;back--)dp[i][j]=(dp[i][j]+(dp[back-1][j-1]*1ll)%mod)%mod;
				continue;
			}
			len=com[j]-com[j-1],cnt=0;
			for(int back=i;back>=1;back--){
				if(v[back].f<=j&&j<=v[back].s)cnt++;//->can choose
				//cout<<len<<" "<<cnt<<" "<<back<<" "<<dp[back-1][j-1]<<" "<<ncr[len][cnt]<<"B\n";
				dp[i][j]=(dp[i][j]+(dp[back-1][j-1]*(ncr[len][cnt]))%mod)%mod;
			}
		}
		for(int j=1;j<com.size();j++)dp[i][j]=(dp[i][j-1]+dp[i][j])%mod;
	//	for(int j=0;j<com.size();j++)cout<<dp[i][j]<<" ";
	//	cout<<'\n';
	}
	int ans=0;
	for(int i=1;i<=n;i++)ans=(ans+dp[i][com.size()-1])%mod;
	cout<<ans;
}
/*
3
1 3
2 5
1 6
->63
2
1 4
2 5
//1 2 3 4 5
1 1 1 1
//1 2 3 4 5
1 3 4 5 5
->18


dp i = i-1,i
*/

Compilation message (stderr)

boat.cpp: In function 'int32_t main()':
boat.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int j=1;j<com.size();j++)dp[i][j]=(dp[i][j-1]+dp[i][j])%mod;
      |               ~^~~~~~~~~~~
boat.cpp:60:7: warning: unused variable 'sum' [-Wunused-variable]
   60 |   int sum=0;
      |       ^~~
boat.cpp:41:6: warning: unused variable 'm' [-Wunused-variable]
   41 |  int m=inf;
      |      ^

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