제출 #43092

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43092		ffresh	코알라 (JOI13_koala)	C++14	100 / 100	224 ms	10076 KiB

koala

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+15;

#define ll long long


ll tree[N*4];


void update_ind(int pos,int l,int r,int ind,ll upd){
	if(l==r){
		tree[pos] = upd;
		return;
	}
	int mid = (l+r)/2;

	if(ind<=mid){
		update_ind(pos*2,l,mid,ind,upd);
	}
	else
		update_ind(pos*2+1,mid+1,r,ind,upd);
	tree[pos] = max(tree[pos*2],tree[pos*2+1]);
}

ll query(int pos,int l,int r,int ql,int qr){
	if(qr<l || r<ql)return -3e18;

	if(ql<=l && r<=qr){
		return tree[pos];
	}
	int mid = (l+r)/2;
	return max(query(pos*2,l,mid,ql,qr),query(pos*2+1,mid+1,r,ql,qr));
}

ll x[N],b[N];


int main(){
	//freopen("input.txt","r",stdin);
	ll k,m,d,a,n;

	cin>>k>>m>>d>>a>>n;

	for(int i=0;i<N*4;++i)tree[i] = -3e18;

	map<int,int> Hash;
	ll pos = (k/d);
	ll value = -a*pos;
	
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&x[i],&b[i]);
		Hash[x[i]%d];
	}
	x[n+1] = m;
	int ind=0,id;
	Hash[k%d];
	Hash[m%d];
	for(map<int,int>::iterator it= Hash.begin();it!= Hash.end();++it){
		it->second = ind++;
	}
	update_ind(1,0,ind-1,Hash[k%d],-value);

	ll q;
	for(int i=1;i<=n+1;++i){
		id = x[i]%d;
		id = Hash[id];
		pos = (x[i]/d);
		value = -a*pos;
		q = -3e18;
		if(id>0){
			q = query(1,0,ind-1,0,id-1)-a;
		}
		q= max(q,query(1,0,ind-1,id,ind-1)) ;
		q += value + b[i];
		update_ind(1,0,ind-1,id,q-value);
	}
	cout<<q<<endl;

}

컴파일 시 표준 에러 (stderr) 메시지

koala.cpp: In function 'int main()':
koala.cpp:54:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&x[i],&b[i]);
                                ^

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50