# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
464804 | kaxzert | Salesman (IOI09_salesman) | C++17 | 3098 ms | 19212 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
00 00 11 00 00 111111 00000 111111 000000
00 00 1111 0000 11 00 11 11 000000
0000 11 11 00 11 00000 111111 00
00 00 11111111 0000 11 00 11 11 00
00 00 11 11 00 00 111111 00000 11 11 00
**/
#include<bits/stdc++.h>
using namespace std;
void setIO(string s) {
freopen((s+".inp").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
void setIOusaco(string s) {
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ldb long double
#define ii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define fast ios::sync_with_stdio(false); cin.tie(0)
template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}
#define maxN 500008
const ll oo = (ll)1e16;
ll f[maxN];
int n, u, d, s;
int main() {
fast;
cin >> n >> u >> d >> s;
vt<array<int, 3> > a;
a.pb({0, s, 0});
fto(i, 1, n) {
int day, loc, cost;
cin >> day >> loc >> cost;
a.pb({day, loc, cost});
}
a.pb({600000, s, 0});
sort(all(a), [](array<int, 3> a, array<int, 3> b) {
return a[0] < b[0];
});
// trav(i, a) {
// cout << i[0] << " " << i[1] << " " << i[2] << '\n';
// }
fto(i, 0, sz(a)-1) f[i] = -oo;
f[0] = 0;
fto(i, 1, sz(a)-1) {
fto(j, 0, i-1) {
if (a[i][1] < a[j][1]) {
f[i] = max(f[i], f[j] + a[i][2] -(a[j][1]-a[i][1])*u);
} else {
f[i] = max(f[i], f[j] + a[i][2] -(a[i][1]-a[j][1])*d);
}
}
}
cout << f[sz(a)-1] << '\n';
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |