oj.uz

답안 #986365

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
986365 2024-05-20T11:17:50 Z Pyqe 휴가 (IOI14_holiday) C++17
100 / 100
 1630 ms 8020 KB 
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long nn=0,p[2],sm,dd,inf=1e18;
queue<pair<pair<long long,long long>,pair<long long,long long>>> q;
multiset<long long> ms[2];
multiset<long long>::iterator it;

void blc()
{
	for(;nn<dd&&!ms[1].empty();nn++)
	{
		it=ms[1].end();
		it--;
		ms[0].insert(*it);
		sm+=*it;
		ms[1].erase(it);
	}
	for(;nn>dd&&!ms[0].empty();nn--)
	{
		it=ms[0].begin();
		ms[1].insert(*it);
		sm-=*it;
		ms[0].erase(it);
	}
}

long long findMaxAttraction(int n, int st, int d, int a[])
{
	long long i,ii,iii,lh,rh,md,lb,rb,w,mx,e,z=-inf;
	pair<long long,long long> mxe;
	
	for(ii=0;ii<2;ii++)
	{
		p[0]=inf;
		q.push({{max(st-d,0),st},{max(st-d,0),n-1}});
		for(;!q.empty();)
		{
			lh=q.front().fr.fr;
			rh=q.front().fr.sc;
			lb=q.front().sc.fr;
			rb=q.front().sc.sc;
			q.pop();
			if(lh>rh)
			{
				continue;
			}
			md=(lh+rh)/2;
			if(md<p[0])
			{
				for(iii=0;iii<2;iii++)
				{
					p[iii]=-iii;
					ms[iii].clear();
				}
				nn=0;
				sm=0;
				dd=d-st+1;
			}
			mxe={-inf,-1};
			for(i=max(lb,md);i<=rb;i++)
			{
				for(;p[1]<i;)
				{
					p[1]++;
					ms[0].insert(a[p[1]]);
					nn++;
					sm+=a[p[1]];
					dd--;
					blc();
				}
				for(;p[0]<md;p[0]++)
				{
					it=ms[0].find(a[p[0]]);
					if(it!=ms[0].end())
					{
						ms[0].erase(it);
						nn--;
						sm-=a[p[0]];
					}
					else
					{
						ms[1].erase(ms[1].find(a[p[0]]));
					}
					dd+=2;
					blc();
				}
				w=sm;
				if(dd<0)
				{
					w=-inf;
				}
				mxe=max(mxe,{w,i});
			}
			mx=mxe.fr;
			e=mxe.sc;
			z=max(z,mx);
			q.push({{lh,md-1},{lb,e}});
			q.push({{md+1,rh},{e,rb}});
		}
		st=n-1-st;
		for(i=0;i<=n/2;i++)
		{
			swap(a[i],a[n-1-i]);
		}
	}
	return z;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 389 ms 6380 KB Output is correct
2 Correct 546 ms 7920 KB Output is correct
3 Correct 383 ms 6188 KB Output is correct
4 Correct 532 ms 8020 KB Output is correct
5 Correct 966 ms 6288 KB Output is correct
6 Correct 131 ms 2712 KB Output is correct
7 Correct 435 ms 3932 KB Output is correct
8 Correct 584 ms 4176 KB Output is correct
9 Correct 80 ms 2128 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 300 ms 7880 KB Output is correct
2 Correct 300 ms 7760 KB Output is correct
3 Correct 397 ms 2944 KB Output is correct
4 Correct 18 ms 960 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 6 ms 856 KB Output is correct
7 Correct 6 ms 860 KB Output is correct
8 Correct 1602 ms 5380 KB Output is correct
9 Correct 1630 ms 5288 KB Output is correct