oj.uz

답안 #131483

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
131483 2019-07-17T08:11:12 Z Mahdi_Jfri 휴가 (IOI14_holiday) C++14
100 / 100
 717 ms 9868 KB 
#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e5 + 20;

ll dp[maxn];

int a[maxn] , d , root , lu[maxn] , ru[maxn] , l[maxn] , r[maxn];

vector<int> pnt , cmp;

void handle(int lux , int rux , int lx , int rx)
{
	if(lx > rx)
		return;
	int k = (lx + rx) / 2;
	l[k] = lx , r[k] = rx , lu[k] = lux , ru[k] = rux;
	pnt.pb(k);
}

ll sum[maxn * 4];
int t[maxn * 4];

void add(int p , int val , int s = 0 , int e = cmp.size() , int v = 1)
{
	if(e - s < 2)
	{
		t[v] += val;
		sum[v] += cmp[s] * val;
		return;
	}

	int m = (s + e) / 2;
	if(p < m)
		add(p , val , s , m , 2 * v);
	else
		add(p , val , m , e , 2 * v + 1);

	t[v] = t[2 * v] + t[2 * v + 1];
	sum[v] = sum[2 * v] + sum[2 * v + 1];
}

ll get(int k , int s = 0 , int e = cmp.size() , int v = 1)
{
	if(k < 0)
		return 0;
	if(k >= t[v])
		return sum[v];
	if(e - s < 2)
		return 1LL * k * cmp[s];

	int m = (s + e) / 2;
	return get(k , m , e , 2 * v + 1) + get(k - t[2 * v + 1] , s , m , 2 * v);
}

long long int findMaxAttraction(int n, int start, int D, int A[])
{
	root = start;
	d = D;

	for(int i = 0; i < n; i++)
		a[i] = A[i] , cmp.pb(a[i]);

	sort(cmp.begin() , cmp.end());
	cmp.resize(unique(cmp.begin() , cmp.end()) - cmp.begin());
	for(int i = 0; i < n; i++)
		a[i] = lower_bound(cmp.begin() , cmp.end() , a[i]) - cmp.begin();

	int ans = 0;
	handle(0 , root , root , n - 1);
	for(;;)
	{
		if(pnt.empty())
			break;

		memset(t , 0 , sizeof t);
		memset(sum , 0 , sizeof sum);

		auto shit = pnt;
		pnt.clear();

		sort(shit.begin() , shit.end());
		int ln = 0 , rn = -1;

		for(auto p : shit)
		{
			while(rn < p)
			{
				rn++;
				add(a[rn] , 1);
			}

			pair<ll , int> upd = {-1 , 0};
			for(int i = lu[p]; i <= ru[p]; i++)
			{
				while(ln < i)
				{
					add(a[ln] , -1);
					ln++;
				}

				int x = d - abs(i - root) - abs(p - root) - min(abs(i - root) , abs(p - root));
				ll sum = get(x);
				upd = max(upd , make_pair(sum , i));
			}

			dp[p] = upd.first;
			handle(lu[p] , upd.second , l[p] , p - 1);
			handle(upd.second , ru[p] , p + 1 , r[p]);
		}
	}

	return *max_element(dp + root , dp + n);
}

Compilation message

holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:73:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans = 0;
      ^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 9272 KB Output is correct
2 Correct 33 ms 9140 KB Output is correct
3 Correct 39 ms 9196 KB Output is correct
4 Correct 40 ms 9200 KB Output is correct
5 Correct 150 ms 8760 KB Output is correct
6 Correct 46 ms 6264 KB Output is correct
7 Correct 81 ms 7284 KB Output is correct
8 Correct 98 ms 7724 KB Output is correct
9 Correct 35 ms 6008 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 7248 KB Output is correct
2 Correct 272 ms 9868 KB Output is correct
3 Correct 256 ms 6544 KB Output is correct
4 Correct 17 ms 5112 KB Output is correct
5 Correct 10 ms 5112 KB Output is correct
6 Correct 10 ms 5112 KB Output is correct
7 Correct 9 ms 5112 KB Output is correct
8 Correct 711 ms 8580 KB Output is correct
9 Correct 717 ms 8388 KB Output is correct