oj.uz

답안 #61044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61044 2018-07-25T06:45:22 Z hamzqq9 휴가 (IOI14_holiday) C++14
100 / 100
 842 ms 10912 KB 
#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define ll long long
#define N 100005
#define orta ((bas+son)>>1)

int Left,Right,n,d,totD,start;
int pos[N];
ll dp[N];
pair<ll,int> attr[N];

struct  SEG {
	
	int ok;
	ll sum;

}S[N*4];

SEG merge(SEG A,SEG B) {

	return {A.ok+B.ok,A.sum+B.sum};

}

ll get(int node,int bas,int son,int val) {

	if(bas==son) return (val>0)*S[node].sum;

	if(S[node*2].ok>val) return get(node*2,bas,orta,val);
	else return get(node*2+1,orta+1,son,val-S[node*2].ok)+S[node*2].sum;

}

void up(int node,int bas,int son,int x,int val) {

	if(bas>x || son<x) return ;

	if(bas==x && son==x) {

		S[node].ok=val;
		S[node].sum=val*attr[bas].st;

		return ;

	}

	up(node*2,bas,orta,x,val);
	up(node*2+1,orta+1,son,x,val);

	S[node]=merge(S[node*2],S[node*2+1]);

}

void up_it() {

	totD=Right-Left+min(start-Left,Right-start);

}

void moveR(int val) {

	while(Right<val) {

		Right++;

		up(1,0,n-1,pos[Right],1);

	}

	while(Right>val) {

		up(1,0,n-1,pos[Right],0);

		Right--;

	}

	up_it();

}

void moveL(int val) {

	while(Left<val) {

		up(1,0,n-1,pos[Left],0);

		Left++;

	}

	while(Left>val) {

		Left--;

		up(1,0,n-1,pos[Left],1);

	}

	up_it();

}

void solve(int bas,int son,int pbas,int pson) {

	if(bas>son) return ;

	moveL(orta);

	int tutP=pbas;
	ll ans=-1;

	for(int i=pbas;i<=pson;i++) {

		moveR(i);

		if(totD>d) break ;

		int rem=d-totD;

		ll res=get(1,0,n-1,min(rem,S[1].ok));

		if(res>=ans) {

			ans=res;
			tutP=i;

		}

	}

	dp[orta]=ans;

	solve(bas,orta-1,pbas,tutP);
	solve(orta+1,son,tutP,pson);

}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {

	ll ans=0;

	::n=n;
	::d=d;
	::start=start;

	for(int i=0;i<n;i++) attr[i]={attraction[i],i};

	sort(attr,attr+n,greater< pair<ll,int> >());

	for(int i=0;i<n;i++) pos[attr[i].nd]=i;

	Right=start-1;
	Left=start+1;

	solve(0,start,start,n-1);

	for(int i=0;i<=start;i++) 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
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 7040 KB Output is correct
2 Correct 63 ms 7136 KB Output is correct
3 Correct 69 ms 7136 KB Output is correct
4 Correct 51 ms 7212 KB Output is correct
5 Correct 99 ms 7212 KB Output is correct
6 Correct 26 ms 7212 KB Output is correct
7 Correct 46 ms 7212 KB Output is correct
8 Correct 46 ms 7212 KB Output is correct
9 Correct 15 ms 7212 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 290 ms 8228 KB Output is correct
2 Correct 53 ms 8228 KB Output is correct
3 Correct 182 ms 8228 KB Output is correct
4 Correct 12 ms 8228 KB Output is correct
5 Correct 5 ms 8228 KB Output is correct
6 Correct 6 ms 8228 KB Output is correct
7 Correct 5 ms 8228 KB Output is correct
8 Correct 842 ms 9960 KB Output is correct
9 Correct 735 ms 10912 KB Output is correct