oj.uz

답안 #98853

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98853 2019-02-26T18:14:03 Z figter001 휴가 (IOI14_holiday) C++14
0 / 100
 5000 ms 5488 KB 
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 1e5+50;

vector<pair<int,int>> a,b;
int s,n,idx[nax],l,r,cnt[4*nax],k;
ll dp[nax],d,seg[4*nax],val;

ll dis(ll a,ll b){
	if(a > b)swap(a,b);
	if(s >= a && s <= b){
		ll go = min(abs(s-b) , abs(s-a));
		ll go2 = max(abs(s-b) , abs(s-a));
		return go*2 + go2;
	}else{
		ll go = max(abs(s-b) , abs(s-a));
		return go;
	}
}

void update(int n,int s,int e){
	if(s > r || e < l)return;
	if(s == e){
		seg[n] = val;
		cnt[n] = (val > 0);
		return;
	}
	update(n*2,s,(s+e)/2);
	update(n*2+1,(s+e)/2+1,e);
	seg[n] = seg[n*2] + seg[n*2+1];
	cnt[n] = cnt[n*2] + cnt[n*2+1];
}

ll get(int n,int s,int e){
	if(s == e){
		if(k == 0)
			return 0;
		else 
			return seg[n];
	}
	if(k > cnt[n*2]){
		k -= cnt[n*2];
		return seg[n*2] + get(n*2+1,(s+e)/2+1,e);
	}else{
		return get(n*2,(s+e)/2+1,e);
	}
}

void solve(int x,int y,int ox,int oy){
	if(x > y)
		return;
	int md = (x+y)/2;
	dp[md] = -1e18;
	int o1 = -1,o2 = -1;
	for(int i=ox;i<=min(oy,md);i++){
		ll rem = d - dis(ox,i);
		l = r = idx[i];
		val = a[i].first;
		update(1,1,n);
		if(rem < 0)continue;
		k = rem;
		ll cur = get(1,1,n);
		if(cur > dp[md]){
			dp[md] = cur;
			o1 = i;
		}
	}
	for(int i=ox;i<=min(oy,md);i++){
		l = r = idx[i];
		val = 0;
		update(1,1,n);
	}
	ll best = -1e18;
	for(int i=min(oy,md);i>=ox;i--){
		ll rem = d - dis(min(oy,md),i);
		l = r = idx[i];
		val = a[i].first;
		update(1,1,n);
		if(rem < 0)continue;
		k = rem;
		ll cur = get(1,1,n);
		// if(x == 0 && y == 4)cout << i << ' ' << cur << ' ' << best << endl;
		if(cur > best){
			best = cur;
			o2 = i;
		}
	}
	for(int i=min(oy,md);i>=ox;i--){
		l = r = idx[i];
		val = 0;
		update(1,1,n);
	}
	// cout << md << ' ' << x << ' ' << y << ' ' << dp[md] << ' ' << o1 << ' ' << o2 << endl;
	dp[md] = max(best,dp[md]);
	solve(x,md-1,ox,o1);
	solve(md+1,y,o2,oy);
}

long long int findMaxAttraction(int N, int start, int days, int attraction[]) {
	n = N;
	s = start;
	d = days;
	for(int i=0;i<n;i++)
		a.push_back({attraction[i],i});
	b = a;
	sort(b.begin(),b.end());
	reverse(b.begin(),b.end());
	for(int i=0;i<n;i++)
		idx[b[i].second] = i+1;
	solve(0,n-1,0,n-1);
	ll ans = 0;
	// printf("\n");
	for(int i=0;i<n;i++){
		// cout << i << ' ' << dp[i] << endl;
		ans = max(ans,dp[i]);
	}
    return ans;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Incorrect 2 ms 384 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

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

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2617 ms 728 KB Output is correct
2 Correct 2047 ms 760 KB Output is correct
3 Correct 2113 ms 760 KB Output is correct
4 Correct 2066 ms 760 KB Output is correct
5 Incorrect 1960 ms 632 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

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