제출 #782605

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
782605		qwerasdfzxcl	코알라 (JOI13_koala)	C++17	100 / 100	63 ms	5860 KiB

koala

#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]);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50