oj.uz

Submission #105726

# Submission time Handle Problem Language Result Execution time Memory
105726 2019-04-14T06:14:32 Z Pro_ktmr Boat (APIO16_boat) C++14
9 / 100
 957 ms 525312 KB 
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define MOD 1000000007

int N;
int a[500],b[500];
vector<int> zaatu;

int dp[2][1005];

int main(){
	
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d%d", a+i, b+i);
		b[i]++;
		//zaatu.PB(a[i]);
		//zaatu.PB(b[i]);
		for(int j=a[i]; j<b[i]; j++) zaatu.PB(j);
	}
	zaatu.PB(0);
	sort(zaatu.begin(), zaatu.end());

	for(int i=0; i<zaatu.size(); i++){
		dp[N%2][i] = 1;
	}
	for(int i=N-1; i>=0; i--){
		for(int j=0; j<zaatu.size(); j++){
			LL ans = dp[(i+1)%2][j];
			for(int k=max(zaatu[j]+1, a[i]); k<b[i]; k++){
				ans += dp[(i+1)%2][lower_bound(zaatu.begin(), zaatu.end(), k)-zaatu.begin()];
				ans %= MOD;
			}
			dp[i%2][j] = ans;
		}
	}

	cout << dp[0][0] - 1 << endl;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<zaatu.size(); i++){
               ~^~~~~~~~~~~~~
boat.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<zaatu.size(); j++){
                ~^~~~~~~~~~~~~
boat.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
boat.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", a+i, b+i);
   ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 256 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 7 ms 256 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 256 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 7 ms 256 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Runtime error 52 ms 7684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 957 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 6 ms 256 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 6 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 7 ms 256 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Runtime error 52 ms 7684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -