| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 838676 | vjudge1 | Salesman (IOI09_salesman) | C++17 | 636 ms | 65536 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define FORE(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define ed << "\n";
#define el cout<<'\n';
#define ALL(s) s.begin(),s.end()
#define fi first
#define se second
#define SQ(a) (a)*(a)
#define A(a) abs(a)
#define SZ(a) ((int)(a.size()))
#define REP(i,a,b) for (int i = (a), _b = (b); i < _b; i++)
#define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define FOD(i,r,l) for(int i=r; i>=l; i--)
#define MASK(x) (1LL << (x))
#define BIT(x, i) ((x) >> (i) & 1)
#define pii pair<int,int>
#define db double
#define II(a, b) make_pair((a),(b))
#define pb(x) push_back(x)
#define int ll
const int mod = 1e9 + 7;
const ll MOD = 1e12 + 7;
const ll INF = 1e18;
/// 998244353;
/// 1e9 + 7;
/// 1e9 + 25;
/// 999999939;
/// 1e12 + 7;
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int random(int l, int r) {
return l + rd() % (r - l + 1);
}
int mul(ll a, ll b) {
if(a >= mod) a %= mod;
if(b >= mod) b %= mod;
return 1LL * a * b % mod;
}
int add(int a, int b) {
a += b;
if(a >= mod) a -= mod;
if(a < 0) a += mod;
return a;
}
int pw(int a, int b) {
int res = 1;
while(b) {
if(b & 1)
res = mul(res, a);
b = b >> 1;
a = mul(a, a);
}
return res;
}
template <class T> inline bool minimize(T &a, const T &b) {
return (a > b ? (a = b),1 : 0);
}
template <class T> inline bool maximize(T &a, const T &b) {
return (a < b ? (a = b),1 : 0);
}
void ReadInp() {
if(fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
#define task "a"
if(fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
#define task "LONG"
if(fopen(task".in","r")) {
freopen(task".in","r",stdin);
freopen(task".out","w",stdout);
}
}
const int maxn = 5e5 + 5;
int n, U, D, S;
int T[maxn];
int L[maxn];
int K[maxn];
int p[maxn];
int f[maxn];
int s[maxn];
vector <pii> event[maxn];
struct BIT{
vector <int> st; int n;
void init(const int sz = 0){
n = sz; st = vector <int> (4 * n + 2, - INF);
}
void upd(int i, int val){
int l = 1, r = n, id = 1;
while(l <= r){
maximize(st[id], val);
int m = (l + r) / 2;
if(l == r) return;
if(i > m){
l = m + 1;
id = id * 2 + 1;
}else{
r = m;
id = id * 2;
}
}
}
int get(int u, int v, int l, int r, int id) const{
if(u <= l && r <= v) return st[id];
if(u > r || v < l) return - INF;
int m = (l + r) / 2;
return max(get(u, v, l, m, id * 2), get(u, v, m + 1, r, id * 2 + 1));
}
int get(int u, int v) const{
return get(u, v, 1, n, 1);
}
}it_D, it_U;
void sol() {
cin >> n >> U >> D >> S;
it_D.init(500000); it_U.init(500000);
memset(f, -0x3f, sizeof f);
swap(U, D);
f[S] = 0; it_D.upd(S, U * S); it_U.upd(S, - D * S);
FOR(i, 1, n){
int t; cin >> t;
int l, m; cin >> l >> m;
event[t].push_back(II(l, m));
}
FOR(i, 1, 500000){
sort(ALL(event[i]));
vector <int> st;
for(auto [Loc, earn] : event[i]){
maximize(f[Loc], it_D.get(1, Loc) - U * Loc + earn);
it_D.upd(Loc, f[Loc] + U * Loc);
}
reverse(ALL(event[i]));
for(auto [Loc, earn] : event[i]){
s[Loc] = it_U.get(Loc, 500000) + D * Loc + earn;
it_U.upd(Loc, s[Loc] - D * Loc);
}
for(auto [Loc, earn] : event[i]){
f[Loc] = max(f[Loc], s[Loc]);
it_U.upd(Loc, f[Loc] - D * Loc);
it_D.upd(Loc, f[Loc] + U * Loc);
}
}
int ans = 0;
FOR(i, 1, 50000) ans = max(ans, f[i] - (S <= i ? (i - S) * D : (S - i) * U));
cout << ans;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
ReadInp();
int t = 1; /// cin >> t;
while(t --) sol();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||