Submission #40964

#	Time	Username	Problem	Language	Result	Execution time	Memory
40964		IvanC	Boat (APIO16_boat)	C++14	0 / 100	238 ms	4628 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN = 502;
const ll MOD = 1e9 + 7;
ll dp[MAXN][2*MAXN],N,M;
ii intervalos[MAXN];
vector<ll> ordenado;
vector<ii> V;
ll inter(ii A,ii B){
	ll l = max(A.first,B.first);
	ll r = min(A.second,B.second);
	if(l > r) return 0;
	return r - l + 1;
}
ll solve(ll i,ll v){
	if(dp[i][v] != -1) return dp[i][v];
	if(inter(V[v],intervalos[i]) == 0) return dp[i][v] = 0;
	ll tot = 1;
	for(ll j = i+1;j<=N;j++){
		for(ll u = v + 1;u<=M;u++){
			tot += solve(j,u);
			tot %= MOD;
		}
	}
	tot *= inter(V[v],intervalos[i]);
	tot %= MOD;
	return dp[i][v] = tot;
}
int main(){
	cin >> N;
	for(ll i = 1;i<=N;i++){
		cin >> intervalos[i].first >> intervalos[i].second;
		ordenado.push_back(intervalos[i].first);
		ordenado.push_back(intervalos[i].second);
	}
	sort(ordenado.begin(),ordenado.end());
	ordenado.erase(unique(ordenado.begin(),ordenado.end()),ordenado.end());
	ordenado.push_back(ordenado.back() + 1);
	V.push_back(ii(0,0));
	for(ll i = 0;i+1<ordenado.size();i++){
		V.push_back(ii(ordenado[i],ordenado[i+1] - 1));
	}
	M = V.size();
	memset(dp,-1,sizeof(dp));
	ll ans = 0;
	for(ll i = 1;i<=N;i++){
		for(ll v = 1;v<=M;v++){
			ans += solve(i,v);
			ans %= MOD;
		}
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:42:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(ll i = 0;i+1<ordenado.size();i++){
                  ^

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