oj.uz

Submission #24904

# Submission time Handle Problem Language Result Execution time Memory
24904 2017-06-17T05:38:13 Z kdh9949 코알라 (JOI13_koala) C++14
0 / 100
 109 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 = 1e18;

const int sz = 131072;
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] = 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 = 1; 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
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 Incorrect 0 ms 7584 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7584 KB Output is correct
2 Correct 66 ms 7584 KB Output is correct
3 Correct 29 ms 7584 KB Output is correct
4 Incorrect 63 ms 7584 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 7584 KB Output is correct
2 Correct 106 ms 7584 KB Output is correct
3 Correct 89 ms 7584 KB Output is correct
4 Correct 89 ms 7584 KB Output is correct
5 Incorrect 66 ms 7584 KB Output isn't correct
6 Halted 0 ms 0 KB -