| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 58059 | BrunoPloumhans | Semiexpress (JOI17_semiexpress) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define D(x) //cout << #x << ": " << x << endl
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
os << "{ ";
for(const T& t : v)
os << t << ", ";
return os << "}";
}
template<typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& v) {
return os << "{ " << v.first << ", " << v.second << " }";
}
int n, M, K;
int A, B, C;
int T;
vector<int> express;
vector<vector<pair<int, int>>> impr;
int dp[3042][3042];
void solve(int k, int l, int r, int i, int j) {
//cout << "solve(" << k << ", " << l << ", " << r << ", " << i << ", " << j << ")\n";
if(l > r) return;
int mid = (l+r)/2;
int best = -1;
dp[k][mid] = -1;
for(int x = i; x <= min(j, mid); ++x) {
int nc = dp[k+1][mid-x] + impr[k][x].second;
if(nc >= dp[k][mid]) {
best = x;
dp[k][mid] = nc;
}
}
if(l == r) {
return;
}
solve(k, l, mid-1, i, best);
solve(k, mid+1, r, best, j);
}
int time(int p1, int p2, int p3) {
return p1*B + (p2-p1)*C + (p3-p2)*A;
}
signed main() {
ios_base::sync_with_stdio(false);
cin >> n >> M >> K >> A >> B >> C >> T;
K -= M;
impr.resize(M);
express.resize(M);
for(int i = 0; i < M; ++i) {
cin >> express[i];
--express[i];
impr[i].push_back({express[i], (express[i]*B <= T)});
}
for(int seg = 0; seg < M-1; ++seg) {
int pos = express[seg]+1;
while(pos < express[seg+1] && impr[seg].size() <= K) {
int timeToPos = time(express[seg], impr[seg].back().first, pos);
if(timeToPos <= T) {
++impr[seg].back().second;
} else if(time(express[seg], pos, pos) <= T) {
impr[seg].push_back({pos, pos - express[seg]+1});
}
++pos;
}
}
D(impr);
for(int i = 0; i <= K; ++i) {
dp[M-1][i] = impr[M-1][0].second;
}
for(int i = M-2; i >= 0; --i) {
solve(i, 0, K, 0, impr[i].size()-1);
}
cout << dp[0][K]-1 << endl;
assert(dp[0][K] <= N);
/*for(int i = 0; i < M; ++i) {
for(int j = 0; j <= K; ++j) {
cout << dp[i][j] << " ";
}
cout << endl;
}*/
return 0;
}