oj.uz

Submission #83360

# Submission time Handle Problem Language Result Execution time Memory
83360 2018-11-07T10:32:57 Z farukkastamonuda Holiday (IOI14_holiday) C++14
100 / 100
 735 ms 13324 KB 
#include "holiday.h"
#include <bits/stdc++.h>
#define li 100005
#define inf 2000001000
#define md 1000000007
#define lo long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ii pair<lo int,lo int>
#define orta (bas+son)/2
#define mid (start+end)/2
using namespace std;
int Left,Right,n,d,start,pos[li],totD,g[105];
lo int dp[li];
pair<lo int, int> at[li];
struct SEG{
	int ok;
	lo int sum;
}tree[li*4];
SEG merge(SEG a,SEG b){
	return {a.ok+b.ok,a.sum+b.sum};
}
lo int get(int node,int start,int end,int val){
	if(start==end) return (val>0)*tree[node].sum;
	if(tree[node*2].ok>val){
		return get(node*2,start,mid,val);
	}
	else return get(node*2+1,mid+1,end,val-tree[node*2].ok)+tree[node*2].sum;
	
}
void update(int node,int start,int end,int x,int val){
	if(start>end || start>x || end<x) return ;
	if(start==x && end==x){
		tree[node].ok=val;
		tree[node].sum=val*at[start].fi;
		return ;
	}
	update(node*2,start,mid,x,val),update(node*2+1,mid+1,end,x,val);
	tree[node]=merge(tree[node*2],tree[node*2+1]);
}
void up_it(){
	totD=Right-Left+min(start-Left,Right-start);
}
void moveR(int x){
	while(Right<x){
		Right++;
		update(1,0,n-1,pos[Right],1);
	}
	while(Right>x){
		update(1,0,n-1,pos[Right],0);
		Right--;
	}
	up_it();
}
void moveL(int x){
	while(Left<x){
		update(1,0,n-1,pos[Left],0);
		Left++;
	}
	while(Left>x){
		Left--;
		update(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;
	lo int ans=-1;
	for(int i=pbas;i<=pson;i++){
		moveR(i);
		if(totD>d) break;
		int rem=d-totD;
		lo int res=get(1,0,n-1,min(rem,tree[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[]){
	::n=n;
	::d=d;
	::start=start;
	lo int ans=0;
	for(int i=0;i<n;i++) at[i]=mp(attraction[i],i);
	sort(at,at+n,greater< pair<lo int,int> >());
	for(int i=0;i<n;i++) pos[at[i].se]=i;
	Left=start+1;
	Right=start-1;
	solve(0,start,start,n-1);
	for(int i=0;i<=start;i++) ans=max(ans,dp[i]);
	return ans;
}
//~ int main(){
	//~ g[0]=10,g[1]=2,g[2]=20,g[3]=30,g[4]=1;
	//~ lo int ty=findMaxAttraction(5,2,7,g);
	//~ printf("%lld\n",ty);
	//~ return 0;
//~ }

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 636 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 7388 KB Output is correct
2 Correct 73 ms 7548 KB Output is correct
3 Correct 57 ms 7832 KB Output is correct
4 Correct 54 ms 8212 KB Output is correct
5 Correct 72 ms 8212 KB Output is correct
6 Correct 22 ms 8212 KB Output is correct
7 Correct 49 ms 8212 KB Output is correct
8 Correct 49 ms 8212 KB Output is correct
9 Correct 15 ms 8212 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8212 KB Output is correct
2 Correct 6 ms 8212 KB Output is correct
3 Correct 6 ms 8212 KB Output is correct
4 Correct 14 ms 8212 KB Output is correct
5 Correct 11 ms 8212 KB Output is correct
6 Correct 4 ms 8212 KB Output is correct
7 Correct 4 ms 8212 KB Output is correct
8 Correct 6 ms 8212 KB Output is correct
9 Correct 5 ms 8212 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 10712 KB Output is correct
2 Correct 57 ms 10792 KB Output is correct
3 Correct 158 ms 10792 KB Output is correct
4 Correct 12 ms 10792 KB Output is correct
5 Correct 5 ms 10792 KB Output is correct
6 Correct 5 ms 10792 KB Output is correct
7 Correct 5 ms 10792 KB Output is correct
8 Correct 735 ms 12512 KB Output is correct
9 Correct 644 ms 13324 KB Output is correct