oj.uz

답안 #732930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
732930 2023-04-29T15:13:28 Z myrcella 휴가 (IOI14_holiday) C++17
100 / 100
 1040 ms 5768 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

set <pii> ss1,ss2;
vector <int> val;

ll ans = 0,curans = 0;
int curl,curr;
int p,w;

void add(int pos) {
	int tmp = val[pos];
	if (!ss1.empty() and tmp>(*ss1.begin()).fi) ss1.insert({tmp,pos}),curans += tmp;
	else ss2.insert({tmp,pos});
}

void bye(int pos) {
	int tmp = val[pos];
	if (ss1.find(MP(tmp,pos))!=ss1.end()) curans -= tmp, ss1.erase(MP(tmp,pos));
	else ss2.erase(MP(tmp,pos));
}

void modify(int sz) {
	assert(sz>=0);
	while (SZ(ss1)<sz and !ss2.empty()) {
		auto tmp = (*(--ss2.end()));
		ss2.erase(--ss2.end());
		ss1.insert(tmp);
		curans += tmp.fi;
	}
	while (SZ(ss1)>sz) {
		auto tmp = (*ss1.begin());
		ss1.erase(ss1.begin());
		ss2.insert(tmp);
		curans -= tmp.fi;
	}
}

void dnc(int lmin,int lmax,int rl,int rr,int cop,int col,int cor) {
	
	if (lmin>lmax) return;
	int cur = lmin+lmax>>1;
	while (curl>cur) add(--curl);
	while (curl<cur) bye(curl++);
	while (curr>rr) bye(curr--);
	while (curr<rl) add(++curr);
	int opt = -1;
	ll optval = -1;
	int sz = w-(cop*p+col*cur+cor*curr);
	if (curr==rl) {
		while (1) {
			if (sz>=0) {
				modify(sz);
				if (curans > optval) optval = curans,opt = curr;
			}
			if (curr!=rr) add(++curr);
			else break;
			sz-=cor;
		}
	}
	else {
		assert(curr==rr);
		while (1) {
			if (sz>=0) {
				modify(sz);
				if (curans > optval) optval = curans,opt = curr;
			}
			if (curr!=rl) bye(curr--);
			else break;
			sz+=cor;
		}
	}
	assert(opt!=-1);
//	cout<<lmin<<" "<<lmax<<" "<<rl<<" "<<rr<<" "<<opt<<" "<<optval<<endl;
	ans = max(ans,optval);
	if (curr==rl) dnc(lmin,cur-1,rl,opt,cop,col,cor),dnc(cur+1,lmax,opt,rr,cop,col,cor);
	else dnc(cur+1,lmax,opt,rr,cop,col,cor),dnc(lmin,cur-1,rl,opt,cop,col,cor);
}

ll findMaxAttraction(int n,int start,int d,int* attraction) {
	if (d==0) return 0;
	rep(i,0,n) val.pb(attraction[i]);
	p = start,w=d;
	curl = curr = p;
	curans = val[p];
	ss1.insert({val[p],p});
	dnc(max(0,p-d/2),p,p,n-1,1,-2,1);
	curl = curr = p;
	curans = val[p];
	while (!ss2.empty()) ss2.erase(ss2.begin());
	while (!ss1.empty()) ss1.erase(ss1.begin());
	ss1.insert({val[p],p});
	dnc(max(0,p-d),p,p,n-1,-1,-1,2);
	return ans;
}

Compilation message

holiday.cpp: In function 'void dnc(int, int, int, int, int, int, int)':
holiday.cpp:62:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |  int cur = lmin+lmax>>1;
      |            ~~~~^~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 5700 KB Output is correct
2 Correct 52 ms 5656 KB Output is correct
3 Correct 59 ms 5768 KB Output is correct
4 Correct 51 ms 5700 KB Output is correct
5 Correct 77 ms 5296 KB Output is correct
6 Correct 15 ms 2176 KB Output is correct
7 Correct 37 ms 3372 KB Output is correct
8 Correct 50 ms 3984 KB Output is correct
9 Correct 11 ms 1772 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 724 KB Output is correct
2 Correct 9 ms 724 KB Output is correct
3 Correct 6 ms 724 KB Output is correct
4 Correct 15 ms 824 KB Output is correct
5 Correct 12 ms 724 KB Output is correct
6 Correct 3 ms 692 KB Output is correct
7 Correct 5 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 5 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 339 ms 5736 KB Output is correct
2 Correct 56 ms 5748 KB Output is correct
3 Correct 160 ms 1636 KB Output is correct
4 Correct 10 ms 784 KB Output is correct
5 Correct 5 ms 688 KB Output is correct
6 Correct 5 ms 724 KB Output is correct
7 Correct 5 ms 692 KB Output is correct
8 Correct 1040 ms 5356 KB Output is correct
9 Correct 1004 ms 5444 KB Output is correct