Submission #1242970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242970		shiori_chan	코알라 (JOI13_koala)	C++20	100 / 100	98 ms	12736 KiB

koala

#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <chrono>
#include <map>
#define all(x) x.begin(), x.end()
#define compact(x) x.erase(unique(all(x)) , x.end())

using namespace std;
typedef long long ll;
#define int long long

const int nd = 1e5 + 5 , INF = 1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> dist(1 , (int)2e9);

struct node{
	int T , B , id;
	node(){}
	node(int T , int B) : T(T) , B(B){}
} point[nd];

struct segment_tree{
	int n; 
	vector <int> st;

	segment_tree(int _n , int v){
		n = _n;
		st.resize(4 * (n + 1) , v);
	}

	void up(int id , int l , int r , int x , int v){
		if(l > x || r < x) return;
		if(l == r){
			st[id] = v;
			return;
		}
		int mid = (r + l) / 2;
		up(id * 2 , l , mid , x , v); up(id * 2 + 1 , mid + 1 , r , x , v);
		st[id] = max(st[id * 2] , st[id * 2 + 1]);
	}

	int get(int id , int l , int r , int a , int b){
		if(l > b || r < a) return - INF;
		if(a <= l && r <= b) return st[id];
		int mid = (r + l) / 2;
		return max(get(id * 2 , l , mid , a , b) , get(id * 2 + 1 , mid + 1 , r , a , b));
	}
};

map <int , int> mp;
int dp[nd];

void solve(){
	int D , M , K , A , N;
	cin >> K >> M >> D >> A >> N;
	if(N <= 1000){
		dp[0] = 0;
		point[0] = node(K , 0);
		for(int i = 1;i <= N; ++ i) cin >> point[i].T >> point[i].B;
		++ N;
		point[N] = node(M , 0);

		for(int i = 1;i <= N; ++ i){
			dp[i] = -INF;
			for(int j = i - 1;j >= 0; -- j){
				dp[i] = max(dp[i] , dp[j] - A * ((point[i].T - point[j].T) / D + ((point[i].T - point[j].T) % D != 0)));
				//cout << point[i].T << " " << point[j].T << " " << dp[i] <<'\n'; 
			}
			dp[i] += point[i].B;
		}

		cout << dp[N];
		return;
	}

	++ N;

	segment_tree seg(N , -INF);
	vector <int> tmp;
	point[N] = node(M , 0);
	tmp.push_back(K % D);
	tmp.push_back(-1);

	for(int i = 1;i <= N; ++ i) 
		cin >> point[i].T >> point[i].B , point[i].id = point[i].T / D ,
		tmp.push_back(point[i].T % D);
	
	sort(all(tmp)); compact(tmp);
	for(int i = 0;i < tmp.size(); ++ i) mp[tmp[i]] = i;

	seg.up(1 , 1 , N , mp[K % D] , (K / D) * A);

	for(int i = 1 ; i <= N; ++ i){
		int x = mp[point[i].T % D];
		
		int ans = max(seg.get(1 , 1 , N , 1 , x - 1) - A , seg.get(1 , 1 , N , x , N));
		ans += point[i].B - (point[i].T / D) * A;
		seg.up(1 , 1 , N , x , ans + (point[i].T / D) * A);

		if(i == N) cout << ans;
	}
}

signed main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);

	#define task "task" 
	if(fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}
	solve();

	return 0;
}

Compilation message (stderr)

koala.cpp: In function 'int main()':
koala.cpp:112:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |                 freopen(task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
koala.cpp:113:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |                 freopen(task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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