Submission #187540

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
187540	2020-01-13T03:01:44 Z	dndhk	Watching (JOI13_watching)	C++14	100 / 100	230 ms	16248 KB

watching

#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});
}

int dp[MAX_N+1][MAX_N+1];

bool chk(ll x){
	for(int i=0; i<=N; i++){
		for(int j=0; j<=min(N, P); j++){
			dp[i][j] = INFLL;
		}
	}
	//cout<<x<<endl;
	int r1=0, r2=0;
	dp[0][0] = 0;
	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--){
			if(dp[i][j]==INFLL)	continue;
			if(i==N){
				if(j<=P && dp[i][j]<=Q)	return true;
			}else{
				if(dp[i][j]>Q)	continue;
				dp[r1][j+1] = min(dp[r1][j+1], dp[i][j]);
				dp[r2][j] = min(dp[r2][j], dp[i][j]+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:37: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:40: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:58: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:61: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

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	888 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	3 ms	888 KB	Output is correct
5	Correct	4 ms	888 KB	Output is correct
6	Correct	3 ms	888 KB	Output is correct
7	Correct	2 ms	760 KB	Output is correct
8	Correct	3 ms	760 KB	Output is correct
9	Correct	3 ms	860 KB	Output is correct
10	Correct	3 ms	888 KB	Output is correct
11	Correct	3 ms	888 KB	Output is correct
12	Correct	3 ms	888 KB	Output is correct
13	Correct	1 ms	888 KB	Output is correct
14	Correct	3 ms	760 KB	Output is correct
15	Correct	2 ms	760 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	14 ms	8520 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	182 ms	15992 KB	Output is correct
4	Correct	210 ms	16116 KB	Output is correct
5	Correct	28 ms	9080 KB	Output is correct
6	Correct	230 ms	16148 KB	Output is correct
7	Correct	13 ms	8568 KB	Output is correct
8	Correct	29 ms	9464 KB	Output is correct
9	Correct	77 ms	14376 KB	Output is correct
10	Correct	143 ms	16120 KB	Output is correct
11	Correct	30 ms	9208 KB	Output is correct
12	Correct	136 ms	16248 KB	Output is correct
13	Correct	12 ms	8568 KB	Output is correct
14	Correct	13 ms	8696 KB	Output is correct
15	Correct	12 ms	8568 KB	Output is correct