oj.uz

Submission #782605

# Submission time Handle Problem Language Result Execution time Memory
782605 2023-07-14T06:24:32 Z qwerasdfzxcl 코알라 (JOI13_koala) C++17
100 / 100
 63 ms 5860 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
int X[100100], B[100100];
ll dp[100100];

struct Seg{
	ll tree[300300];
	int sz;
	
	void init(int n){
		sz = n;
		fill(tree, tree+sz*2, -INF);
	}

	void update(int p, ll x){
		p += sz;
		tree[p] = max(tree[p], x);
		for (p>>=1;p;p>>=1) tree[p] = max(tree[p<<1], tree[p<<1|1]);
	}

	ll query(int l, int r){
		++r;
		ll ret = -INF;
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1) ret = max(ret, tree[l++]);
			if (r&1) ret = max(ret, tree[--r]);
		}

		return ret;
	}
}tree;

int main(){
	int _s, _e, k, A, n;
	scanf("%d %d %d %d %d", &_s, &_e, &k, &A, &n);

	X[0] = _s;
	X[n+1] = _e;

	for (int i=1;i<=n;i++){
		scanf("%d %d", X+i, B+i);
	}

	vector<int> C;
	for (int i=0;i<=n+1;i++){
		C.push_back(X[i] % k);
	}

	sort(C.begin(), C.end());
	C.erase(unique(C.begin(), C.end()), C.end());
	tree.init(C.size() + 10);

	int idx0 = lower_bound(C.begin(), C.end(), X[0] % k) - C.begin() + 1;
	tree.update(idx0, (ll)(X[0]/k) * A);

	for (int i=1;i<=n+1;i++){
		dp[i] = -INF;

		// naive

		// for (int j=0;j<i;j++){
		// 	if (X[i] % k > X[j] % k){
		// 		dp[i] = max(dp[i], (dp[j] + (ll)(X[j]/k) * A) - ((ll)(X[i]/k) * A + A - B[i]));
		// 	}
		// 	else{
		// 		dp[i] = max(dp[i], (dp[j] + (ll)(X[j]/k) * A) - ((ll)(X[i]/k) * A - B[i]));
		// 	}
		// }

		int idx = lower_bound(C.begin(), C.end(), X[i] % k) - C.begin() + 1;
		dp[i] = max(dp[i], tree.query(1, idx-1) - ((ll)(X[i]/k) * A + A - B[i]));
		dp[i] = max(dp[i], tree.query(idx, (int)C.size()) - ((ll)(X[i]/k) * A - B[i]));

		tree.update(idx, dp[i] + (ll)(X[i]/k) * A);
	}

	printf("%lld\n", dp[n+1]);
}

Compilation message

koala.cpp: In function 'int main()':
koala.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d %d %d %d %d", &_s, &_e, &k, &A, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d %d", X+i, B+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 324 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2500 KB Output is correct
2 Correct 27 ms 3916 KB Output is correct
3 Correct 15 ms 2804 KB Output is correct
4 Correct 33 ms 4248 KB Output is correct
5 Correct 16 ms 2768 KB Output is correct
6 Correct 10 ms 1744 KB Output is correct
7 Correct 17 ms 3256 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 3528 KB Output is correct
2 Correct 63 ms 5692 KB Output is correct
3 Correct 50 ms 5860 KB Output is correct
4 Correct 53 ms 5832 KB Output is correct
5 Correct 33 ms 3744 KB Output is correct
6 Correct 24 ms 2800 KB Output is correct