oj.uz

답안 #187538

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
187538 2020-01-13T02:56:26 Z dndhk 구경하기 (JOI13_watching) C++14
50 / 100
 1000 ms 504 KB 
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 2002;
const ll INFLL = 10000;
int N, P, Q;
vector<ll> v;

list<pii> dq[2][MAX_N+1];

void add(int idx, int x, int y, int z){
	while(!dq[idx][x].empty() && dq[idx][x].back().first>=z){
		dq[idx][x].pop_back();
	}
	dq[idx][x].push_back({z, y});
}

bool chk(ll x){
	for(int i=0; i<=N; i++){
		while(!dq[0][i].empty())	dq[0][i].pop_back();
		while(!dq[1][i].empty())	dq[1][i].pop_back();
	}
	dq[0][0].pb({0, 0});
	//cout<<x<<endl;
	int r1=0, r2=0, k;
	for(int i=0; i<=N; i++){
		while(r1<v.size()-1 && v[r1+1]<=v[i+1]+x-1LL){
			r1++;
		}
		while(r2<v.size()-1 && v[r2+1]<=v[i+1]+2LL*x-1LL){
			r2++;
		}
		for(int j=min(i, P); j>=0; j--){
			while(!dq[0][j].empty() && dq[0][j].front().second<i)	dq[0][j].pop_front();
			while(!dq[1][j].empty() && dq[1][j].front().second<i)	dq[1][j].pop_front();
			if(dq[0][j].empty()){
				if(!dq[1][j].empty())	k = dq[1][j].front().first;
				else continue;
			}else{
				if(dq[1][j].empty())	k = dq[0][j].front().first;
				else{
					k = min(dq[0][j].front().first, dq[1][j].front().first);
				}
			}
			if(i==N){
				if(j<=P && k<=Q)	return true;
			}else{
				if(k>Q)	continue;
				add(0, j+1, r1, k);
				add(1, j, r2, k+1);
			}
		}
	}
	return false;
}

int main(){
	scanf("%d%d%d", &N, &P, &Q);	
	v.pb(0);
	for(int i=1; i<=N; i++){
		ll x; scanf("%lld", &x);
		v.pb(x);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	sort(v.begin(), v.end());
	N = v.size()-1;
	ll s = 1LL, e = 1000000000LL, m;
	while(s<e){
		m = (s+e)/2LL;
		if(chk(m)){
			e = m;
		}else{
			s = m+1;
		}
	}
	printf("%lld", s);
}

Compilation message

watching.cpp: In function 'bool chk(ll)':
watching.cpp:34:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(r1<v.size()-1 && v[r1+1]<=v[i+1]+x-1LL){
         ~~^~~~~~~~~~~
watching.cpp:37:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(r2<v.size()-1 && v[r2+1]<=v[i+1]+2LL*x-1LL){
         ~~^~~~~~~~~~~
watching.cpp: In function 'int main()':
watching.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &P, &Q); 
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll x; scanf("%lld", &x);
         ~~~~~^~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 15 ms 504 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 4 ms 376 KB Output is correct
11 Correct 10 ms 376 KB Output is correct
12 Correct 11 ms 376 KB Output is correct
13 Correct 3 ms 484 KB Output is correct
14 Correct 4 ms 376 KB Output is correct
15 Correct 4 ms 376 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Execution timed out 1034 ms 504 KB Time limit exceeded
4 Halted 0 ms 0 KB -