제출 #1344992

#제출 시각아이디문제언어결과실행 시간메모리
1344992nanaseyuzukiSalesman (IOI09_salesman)C++20
60 / 100
345 ms56016 KiB
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e18;

int n, up, down, s, pre[mn], suf[mn];

struct Festival {
	int t, l, m;

	bool operator< (const Festival& other) const {
		if(t == other.t) return l < other.l;
		return t < other.t;
	}
} e[mn];

vector <Festival> event[mn];

struct SegTree {
	int st[mn << 2];

	void build(int id, int l, int r) {
		if(l == r) {
			st[id] = - inf;
			return; 
		}
		int mid = (l + r) >> 1;
		build(id << 1, l, mid);
		build(id << 1 | 1, mid + 1, r);
		st[id] = max(st[id << 1], st[id << 1 | 1]);
	}

	void update(int id, int l, int r, int pos, int val, int flag) {
		if(l > pos || r < pos) return;
		if(l == r) {
			if(flag) st[id] = max(st[id], val - l * down);
			else st[id] = max(st[id], val + l * up);
			return;
		}
		int mid = (l + r) >> 1;
		update(id << 1, l, mid, pos, val, flag);
		update(id << 1 | 1, mid + 1, r, pos, val, flag);
		st[id] = max(st[id << 1], st[id << 1 | 1]);
	} 

	int get(int id, int l, int r, int u, int v) {
		if(l > v || r < u) return - inf;
		if(l >= u && r <= v) return st[id];
		int mid = (l + r) >> 1;
		return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
	}
} lef, rig;

void solve() {
    cin >> n >> down >> up >> s;
    for(int i = 1; i <= n; i++) {
    	cin >> e[i].t >> e[i].l >> e[i].m;
    	event[e[i].t].push_back(e[i]);
    }
    lef.build(1, 1, 5e5), rig.build(1, 1, 5e5);
    lef.update(1, 1, 5e5, s, 0, 0);
    rig.update(1, 1, 5e5, s, 0, 1);

    for(int t = 1; t <= 5e5; t++) {
    	if(event[t].empty()) continue;
    	sort(all(event[t]));
    	
    	int cnt = 0;
    	for(auto [Kazuki, l, m] : event[t]) {
    		pre[cnt] = suf[cnt] = max(lef.get(1, 1, 5e5, 1, l) - l * up + m, rig.get(1, 1, 5e5, l, 5e5) + l * down + m);
    		// cout << lef.get(1, 1, 5e5, 1, l) << ' ' << rig.get(1, 1, 5e5, l, 5e5) << '\n';
    		cnt ++;
    	}

    	for(int i = 1; i < cnt; i++) pre[i] = max(pre[i], pre[i - 1] - (event[t][i].l - event[t][i - 1].l) * up);
    	for(int i = cnt - 2; i >= 0; i--) suf[i] = max(suf[i], suf[i + 1] - (event[t][i + 1].l - event[t][i].l) * down);
    	// cout << cnt << ' ' << pre[0] << ' ' << suf[0] << '\n';
    	for(int i = 0; i < cnt; i++) {
    		int val = max(pre[i], suf[i]);
    		lef.update(1, 1, 5e5, event[t][i].l, val, 0);
    		rig.update(1, 1, 5e5, event[t][i].l, val, 1);
    	}
	}
	cout << max(lef.get(1, 1, 5e5, 1, s) - s * up, rig.get(1, 1, 5e5, s, 5e5) + s * down) << '\n';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    #define task "Kawabata"
    if (fopen(task".INP", "r")) {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro

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

salesman.cpp: In function 'int main()':
salesman.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...