oj.uz

Submission #24912

# Submission time Handle Problem Language Result Execution time Memory
24912 2017-06-17T05:48:03 Z kdh9949 코알라 (JOI13_koala) C++14
100 / 100
 96 ms 7584 KB 
#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

koala.cpp: In function 'int main()':
koala.cpp:28:49: 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:40: 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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7584 KB Output is correct
2 Correct 0 ms 7584 KB Output is correct
3 Correct 0 ms 7584 KB Output is correct
4 Correct 0 ms 7584 KB Output is correct
5 Correct 3 ms 7584 KB Output is correct
6 Correct 0 ms 7584 KB Output is correct
7 Correct 0 ms 7584 KB Output is correct
8 Correct 0 ms 7584 KB Output is correct
9 Correct 0 ms 7584 KB Output is correct
10 Correct 0 ms 7584 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 7584 KB Output is correct
2 Correct 76 ms 7584 KB Output is correct
3 Correct 36 ms 7584 KB Output is correct
4 Correct 73 ms 7584 KB Output is correct
5 Correct 46 ms 7584 KB Output is correct
6 Correct 26 ms 7584 KB Output is correct
7 Correct 39 ms 7584 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7584 KB Output is correct
2 Correct 89 ms 7584 KB Output is correct
3 Correct 96 ms 7584 KB Output is correct
4 Correct 83 ms 7584 KB Output is correct
5 Correct 63 ms 7584 KB Output is correct
6 Correct 43 ms 7584 KB Output is correct