oj.uz

Submission #40964

# Submission time Handle Problem Language Result Execution time Memory
40964 2018-02-10T15:03:20 Z IvanC Boat (APIO16_boat) C++14
0 / 100
 238 ms 4628 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];
	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

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.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 4216 KB Output is correct
2 Correct 184 ms 4320 KB Output is correct
3 Correct 186 ms 4420 KB Output is correct
4 Correct 177 ms 4440 KB Output is correct
5 Correct 187 ms 4440 KB Output is correct
6 Correct 236 ms 4444 KB Output is correct
7 Correct 233 ms 4448 KB Output is correct
8 Correct 235 ms 4572 KB Output is correct
9 Correct 230 ms 4572 KB Output is correct
10 Correct 238 ms 4628 KB Output is correct
11 Correct 235 ms 4628 KB Output is correct
12 Correct 226 ms 4628 KB Output is correct
13 Correct 234 ms 4628 KB Output is correct
14 Correct 230 ms 4628 KB Output is correct
15 Correct 236 ms 4628 KB Output is correct
16 Incorrect 45 ms 4628 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 4216 KB Output is correct
2 Correct 184 ms 4320 KB Output is correct
3 Correct 186 ms 4420 KB Output is correct
4 Correct 177 ms 4440 KB Output is correct
5 Correct 187 ms 4440 KB Output is correct
6 Correct 236 ms 4444 KB Output is correct
7 Correct 233 ms 4448 KB Output is correct
8 Correct 235 ms 4572 KB Output is correct
9 Correct 230 ms 4572 KB Output is correct
10 Correct 238 ms 4628 KB Output is correct
11 Correct 235 ms 4628 KB Output is correct
12 Correct 226 ms 4628 KB Output is correct
13 Correct 234 ms 4628 KB Output is correct
14 Correct 230 ms 4628 KB Output is correct
15 Correct 236 ms 4628 KB Output is correct
16 Incorrect 45 ms 4628 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 4216 KB Output is correct
2 Correct 184 ms 4320 KB Output is correct
3 Correct 186 ms 4420 KB Output is correct
4 Correct 177 ms 4440 KB Output is correct
5 Correct 187 ms 4440 KB Output is correct
6 Correct 236 ms 4444 KB Output is correct
7 Correct 233 ms 4448 KB Output is correct
8 Correct 235 ms 4572 KB Output is correct
9 Correct 230 ms 4572 KB Output is correct
10 Correct 238 ms 4628 KB Output is correct
11 Correct 235 ms 4628 KB Output is correct
12 Correct 226 ms 4628 KB Output is correct
13 Correct 234 ms 4628 KB Output is correct
14 Correct 230 ms 4628 KB Output is correct
15 Correct 236 ms 4628 KB Output is correct
16 Incorrect 45 ms 4628 KB Output isn't correct
17 Halted 0 ms 0 KB -