oj.uz

Submission #52370

# Submission time Handle Problem Language Result Execution time Memory
52370 2018-06-25T16:17:33 Z pzdba Boat (APIO16_boat) C++14
0 / 100
 8 ms 2296 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod = 1e9+7;

int a[505], b[505];

map<int, int> ht;
map<int, int>::iterator its;
int rev[1005];

int dp[505][1005];

int main(){
	int n;
	scanf("%d", &n);
	for(int i=1;i<=n;i++){
		scanf("%d%d", &a[i], &b[i]);
		ht[a[i]] = 1;
		ht[b[i]] = 1;
	}
	int hv = 1;
	for(its = ht.begin();its != ht.end();its++) its->second = hv++, rev[hv-1] = its->first;
	for(int i=1;i<=n;i++) a[i] = ht[a[i]], b[i] = ht[b[i]];
	for(int i=1;i<=n;i++){
		if(i == 1){
			dp[i][0] = 1;
			for(int j=a[i];j<=b[i];j++){
				if(j == a[i]) dp[i][j] = 1;
				else dp[i][j] = (rev[j] - rev[j-1])%mod;
			}
		}
		else{
			dp[i][0] = dp[i-1][0]+1;
			for(int j=a[i];j<=b[i];j++){
				int c = 0;
				if(j == 1) c = 1;
				else c = rev[j]-rev[j-1];
				dp[i][j] = (dp[i][j] + 1)%mod;
				for(int k=0;k<=j-1;k++){
					dp[i][j] = (dp[i][j] + (LL)dp[i-1][k]*c)%mod;
				}
			}
		}
	}
	int ans = 0;
	for(int i=1;i<=2*n;i++){
		ans = (ans + dp[n][i])%mod;
	}
	printf("%d\n", ans);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
boat.cpp:18: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
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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