Submission #145296

#	Time	Username	Problem	Language	Result	Execution time	Memory
145296		gs18103	코알라 (JOI13_koala)	C++14	70 / 100	242 ms	9012 KiB

koala

#include <bits/stdc++.h>
#define fi first
#define se second
#define LINF 1000000000000000000LL
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pll;
 
int t[101010];
ll b[101010], tree[808080];

ll update(int node, int s, int e, int k, ll val) {
	if(s == e) return tree[node] = max(tree[node], val);
	int m = (s + e) >> 1;
	if(k <= m) return tree[node] = max(tree[node*2+1], update(node*2, s, m, k, val));
	else return tree[node] = max(tree[node*2], update(node*2+1, m+1, e, k, val));
}
 
ll cal(int node, int s, int e, int l, int r) {
	if(s > r || e < l) return -LINF;
	if(s >= l && e <= r) return tree[node];
	int m = (s + e) / 2;
	return max(cal(node*2, s, m, l, r), cal(node*2+1, m+1, e, l, r));
}
 
vector <int> num;

int main() {
	int K, m, d, n;
	ll a;
	cin >> K >> m >> d >> a >> n;
	for(int i = 1; i <= n; i++) {
		cin >> t[i] >> b[i];
		t[i] -= K;
		num.eb(t[i]%d);
	}
	num.eb((m-K)%d);
	sort(all(num));
	num.erase(unique(all(num)), num.end());
	for(int i = 0; i < 808080; i++) {
		tree[i] = -LINF;
	}
	update(1, 0, num.size()-1, 0, 0LL);
	for(int i = 1; i < num.size(); i++) {
		update(1, 0, num.size()-1, i, -a);
	}
	for(int i = 1; i <= n; i++) {
		int k = lower_bound(all(num), t[i]%d) - num.begin();
		ll val = cal(1, 0, num.size()-1, k, num.size()-1) + b[i];
		update(1, 0, num.size()-1, k, val);
		update(1, 0, num.size()-1, num.size()-1, val - a);
	}
	int k = lower_bound(all(num), (m-K)%d) - num.begin();
	cout << cal(1, 0, num.size()-1, k, num.size()-1) - a * ((ll)(m - K) / d);
}

Compilation message (stderr)

koala.cpp: In function 'int main()':
koala.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 1; i < num.size(); i++) {
                 ~~^~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 30
• Subtask 3: 50 / 50