Submission #145319

#	Time	Username	Problem	Language	Result	Execution time	Memory
145319		gs18103	코알라 (JOI13_koala)	C++14	100 / 100	99 ms	7856 KiB

koala

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, t[100010];
ll en, d, a, x[100010], b[100010], xx[100010], dp[100010];
const ll inf = 3e18;
 
const int sz = (1 << 17);
struct Seg{
	ll dat[2 * sz];
	void ini(){ fill(dat + 1, dat + 2 * sz, -inf); }
	void upd(int x, ll v){
		x += sz - 1; dat[x] = max(dat[x], v);
		for(x /= 2; x; x /= 2) dat[x] = max(dat[2 * x], dat[2 * x + 1]);
	}
	ll get(int s, int e){
		ll ret = -inf;
		for(s += sz - 1, e += sz - 1; s <= e; s /= 2, e /= 2){
			if(s % 2 == 1) ret = max(ret, dat[s++]);
			if(e % 2 == 0) ret = max(ret, dat[e--]);
		}
		return ret;
	}
} S;
 
int main(){
	scanf("%lld%lld%lld%lld%d", x, &en, &d, &a, &n);
	for(int i = 0; i <= n; i++){
		if(i) scanf("%lld%lld", x + i, b + i);
		x[i] = en - x[i];
		xx[i] = x[i] % d;
	}
	sort(xx, xx + n + 2);
	for(int i = 0; i <= n; i++){
		t[i] = (int)(lower_bound(xx, xx + n + 2, x[i] % d) - xx + 1);
	}
	S.ini();
	S.upd(1, 0);
	for(int i = n; i >= 0; i--){
		dp[i] = max(S.get(t[i], n + 2) - (x[i] / d * a), S.get(1, t[i] - 1) - (x[i] / d * a + a)) + b[i];
		S.upd(t[i], dp[i] + (x[i] / d * a));
	}
	printf("%lld\n", dp[0]);
}

Compilation message (stderr)

koala.cpp: In function 'int main()':
koala.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld%d", x, &en, &d, &a, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   if(i) scanf("%lld%lld", x + i, b + i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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