oj.uz

답안 #419508

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
419508 2021-06-07T08:03:04 Z amunduzbaev 구경하기 (JOI13_watching) C++14
50 / 100
 133 ms 28100 KB 
/* made by amunduzbaev */
 
//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
#include "bits/stdc++.h"
 
using namespace std;
//~ using namespace __gnu_pbds;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define mem(arr, v) memset(arr, v, sizeof arr)
#define int long long
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, true : false; }
template<int sz> using tut = array<int, sz>;
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
//~ template<class T> using oset = tree<T, 
//~ null_type, less_equal<T>, rb_tree_tag, 
//~ tree_order_statistics_node_update>;
 
const int N = 305;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
 
#define MULTI 0
int n, m, k, s, t, q, ans, res, a[N];
bool dp[N][N][N];

bool check(int w){
	mem(dp, 0);
	int l = 1, r = 1;
	for(int i=0;i<=n;i++) dp[0][0][i] = dp[0][i][0] = 1;
	for(int i=1;i<=n;i++){
		while(a[i] - a[l] + 1 > 2 * w) l++;
		while(a[i] - a[r] + 1 > w) r++;
		for(int j=0;j<=q;j++){
			for(int t=0;t<=m;t++){
				if(j) dp[i][j][t] |= dp[l-1][j-1][t];
				if(t) dp[i][j][t] |= dp[r-1][j][t-1];
			}
		}
	}
	
	//~ cout<<w<<"\n";
	//~ for(int i=0;i<=n;i++){
		//~ for(int j=0;j<=q;j++){
			//~ for(int l=0;l<=m;l++){
				//~ cout<<dp[i][j][l]<<" ";
			//~ } cout<<"\n";
		//~ } cout<<"\n";
	//~ } cout<<"\n";
	
	for(int i=1;i<=q;i++){
		for(int j=1;j<=m;j++) if(dp[n][i][j]) return 1;
	} return 0;
}

void solve(int t_case){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(m + q > n) { cout<<1<<"\n"; return; }
	sort(a+1, a+n+1);
	a[0] = a[1];
	//~ check(4);
	
	int l = 1, r = mod;
	while(l + 1 < r){
		int m = (l + r)>>1;
		if(check(m)) r = m;
		else l = m;
	} if(!check(l)) l = r;
	cout<<l<<"\n";
}

signed main(){
	NeedForSpeed
	if(MULTI){
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} else solve(1);
	return 0;
}

Compilation message

watching.cpp: In function 'void usaco(std::string)':
watching.cpp:32:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 | void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:33:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 116 ms 28100 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 115 ms 28060 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 128 ms 28060 KB Output is correct
8 Correct 124 ms 28056 KB Output is correct
9 Correct 121 ms 28056 KB Output is correct
10 Correct 130 ms 28056 KB Output is correct
11 Correct 133 ms 28028 KB Output is correct
12 Correct 129 ms 28064 KB Output is correct
13 Correct 118 ms 28016 KB Output is correct
14 Correct 125 ms 28064 KB Output is correct
15 Correct 120 ms 28056 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 416 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -