oj.uz

Submission #145319

# Submission time Handle Problem Language Result Execution time Memory
145319 2019-08-19T15:07:44 Z gs18103 코알라 (JOI13_koala) C++14
100 / 100
 99 ms 7856 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: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.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 7772 KB Output is correct
2 Correct 72 ms 7516 KB Output is correct
3 Correct 37 ms 5924 KB Output is correct
4 Correct 71 ms 7800 KB Output is correct
5 Correct 43 ms 5720 KB Output is correct
6 Correct 27 ms 4316 KB Output is correct
7 Correct 43 ms 6776 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 7820 KB Output is correct
2 Correct 97 ms 7840 KB Output is correct
3 Correct 93 ms 7856 KB Output is correct
4 Correct 81 ms 7768 KB Output is correct
5 Correct 59 ms 5752 KB Output is correct
6 Correct 46 ms 4984 KB Output is correct