oj.uz

답안 #647868

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
647868 2022-10-04T10:20:35 Z ymm 휴가 (IOI14_holiday) C++17
100 / 100
 3768 ms 7884 KB 
#include"holiday.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100064;
ll mxl[N*2], mxl2[N*2], mxr[N*2], mxr2[N*2];
ll mxc[N];

int bin(int len, ll x)
{
	int l=1, r=len;
	while (l < r) {
		int mid = (l+r)/2;
		if (mxc[mid] - mxc[mid-1] >= x)
			l = mid+1;
		else
			r = mid;
	}
	return l;
}

__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void insert(int len, ll x)
{
	typedef ll ymm __attribute__((vector_size(32),aligned(8)));
	int i = bin(len, x);
	int r = len;
	while ((r-i)%4) {
		mxc[r] = mxc[r-1] + x;
		--r;
	}
	for (; r > i; r -= 4)
		*(ymm *)(mxc+r-3) = *(ymm *)(mxc+r-4) + x;
	mxc[i] = mxc[i-1] + x;
}

template<ll a[2*N]>
__attribute__((optimize("O3,unroll-loops"),target("avx2")))
void up(int len, int off)
{
	#define MAX(x, y) ((x)>(y)?(x):(y))
	Loop (i,0,len)
		a[i+off] = MAX(a[i+off], mxc[i]);
	#undef MAX
}

long long int findMaxAttraction(int n, int s, int d, int attr[])
{
	int k = min(s, n-1-s);
	Loop (i,s+1,n) {
		insert(i - s, attr[i]);
		up<mxr>(i - s + 1, i - s);
		if (i-s <= k)
			up<mxr2>(i - s + 1, 2*(i - s));
	}
	LoopR (i,0,s) {
		insert(s - i, attr[i]);
		up<mxl>(s - i + 1, s - i);
		if (s-i <= k)
			up<mxl2>(s - i + 1, 2*(s - i));
	}
	Loop (i,0,2*N-1) {
		mxl [i+1] = max(mxl [i+1], mxl [i]);
		mxl2[i+1] = max(mxl2[i+1], mxl2[i]);
		mxr [i+1] = max(mxr [i+1], mxr [i]);
		mxr2[i+1] = max(mxr2[i+1], mxr2[i]);
	}
	ll ans = 0;
	Loop (i,0,d+1) {
		if (i < 2*N && (d-i) < 2*N) {
			ans = max(ans, mxl[i] + mxr2[d-i]);
			ans = max(ans, mxl2[i] + mxr[d-i]);
		}
	}
	Loop (i,0,d) {
		if (i < 2*N && (d-1-i) < 2*N) {
			ans = max(ans, mxl[i] + mxr2[d-1-i] + attr[s]);
			ans = max(ans, mxl2[i] + mxr[d-1-i] + attr[s]);
		}
	}
	return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2060 ms 7884 KB Output is correct
2 Correct 2130 ms 7624 KB Output is correct
3 Correct 2001 ms 7636 KB Output is correct
4 Correct 2185 ms 7764 KB Output is correct
5 Correct 2554 ms 7624 KB Output is correct
6 Correct 243 ms 7116 KB Output is correct
7 Correct 747 ms 7428 KB Output is correct
8 Correct 1128 ms 7336 KB Output is correct
9 Correct 117 ms 6988 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2170 ms 7636 KB Output is correct
2 Correct 3768 ms 7692 KB Output is correct
3 Correct 425 ms 7076 KB Output is correct
4 Correct 7 ms 6868 KB Output is correct
5 Correct 6 ms 6868 KB Output is correct
6 Correct 6 ms 6868 KB Output is correct
7 Correct 5 ms 6868 KB Output is correct
8 Correct 2458 ms 7264 KB Output is correct
9 Correct 2390 ms 7388 KB Output is correct