oj.uz

Submission #40963

# Submission time Handle Problem Language Result Execution time Memory
40963 2018-02-10T14:59:54 Z IvanC Boat (APIO16_boat) C++14
0 / 100
 2000 ms 4452 KB 
#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];
	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

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 4344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 4344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 298 ms 4452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 4344 KB Time limit exceeded
2 Halted 0 ms 0 KB -