oj.uz

답안 #49596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49596 2018-05-31T23:29:55 Z wzy Boat (APIO16_boat) C++11
0 / 100
 2000 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define mp make_pair
#define pb push_back
int mod = 1000000007;
int C[600][600];
vector<int> s;
vector<pii> lines;
vector<pii> segments;
int n ;
int dp[200][300][200][3];
bool vis[200][300][200][3];


int custo(int i , int k){
	int U = segments[i].S - segments[i].F+1;
	if(k  > U) return 0;
	return C[U][k];
}

int solve(int i , int j , int k, int w){
	if(j == segments.size()){
		if(w == 0){
			return 0;
		}
		else return 1;
	}
	if(i == n){
		if(w == 0){
			if(k == 0) return 0;
			else return custo(j,k);
		}
		return w;
	}
	if(vis[i][j][k][w]) return dp[i][j][k][w];
	vis[i][j][k][w] = 1;
	if(w){
		 dp[i][j][k][w] = (solve(i, j + 1 , 0 , 1) + solve(i , j , 0 , 0))%mod;
	}
	else{
		dp[i][j][k][w] = solve(i+1,j,k,w);
		dp[i][j][j][w] %= mod;
		if(k > 0){
			dp[i][j][k][w] += solve(i+1,j+1,0,1)*custo(j,k);
			dp[i][j][k][w] %= mod;
		}
		if(lines[i].F <= segments[j].F && lines[i].S >= segments[j].S){
			dp[i][j][k][w] += solve(i+1,j,k+1,0);
			dp[i][j][k][w] %= mod;
		}
	}
	return dp[i][j][k][w];
}


int32_t main(){	
	scanf("%lld" , &n);
	for(int i = 0 ; i < 200 ; i++)
		for(int j = 0 ; j < 300 ; j++)
			for(int k = 0 ; k < 200 ; k++)
				for(int w = 0 ;w < 3 ; w++) dp[i][j][k][w] = 0 , vis[i][j][k][w] = 0;
	// fill C
	for(int i = 0 ; i < 600 ; i++){
		C[i][0] = 1 , C[i][1] = i;
	}
	for(int i = 1 ; i < 600 ; i++){
		for(int j = 2 ; j < i ; j++){
			C[i][j] = C[i-1][j-1] + C[i-1][j];
		}
	}
	//
	lines.resize(n);
	for(int i = 0 ; i < n; i++){
		scanf("%lld%lld", &lines[i].F , &lines[i].S);
		s.pb(lines[i].F) , s.pb(lines[i].S);
	}
	sort(lines.begin() , lines.end());
	for(int i = 0 ; i < s.size() - 1 ; i++){
		segments.pb(pii(s[i] , s[i+1]));
	}
	printf("%lld\n" , solve(0,0,0,1) - segments.size());
}

Compilation message

boat.cpp: In function 'long long int solve(long long int, long long int, long long int, long long int)':
boat.cpp:26:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(j == segments.size()){
     ~~^~~~~~~~~~~~~~~~~~
boat.cpp: In function 'int32_t main()':
boat.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < s.size() - 1 ; i++){
                  ~~^~~~~~~~~~~~~~
boat.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld" , &n);
  ~~~~~^~~~~~~~~~~~~
boat.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &lines[i].F , &lines[i].S);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2119 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2119 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2123 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2119 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -