| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 600696 | 2022-07-21T07:08:05 Z | 반딧불(#8467) | Long Distance Coach (JOI17_coach) | C++17 | 3 ms | 1364 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll X, W, T;
int n, k;
ll arr[200002];
ll off[200002], cost[200002];
ll DP[12][600];
ll ans = 9e18;
int main(){
scanf("%lld %d %d %lld %lld", &X, &k, &n, &W, &T);
for(int i=1; i<=k; i++) scanf("%lld", &arr[i]);
sort(arr+1, arr+k+1);
arr[++k] = X;
for(int i=0; i<n; i++) scanf("%lld %lld", &off[i], &cost[i]);
for(int i=0; i<=k; i++) for(int j=0; j<600; j++) DP[i][j] = 9e18;
DP[0][(1<<n)-1] = W;
for(int i=1; i<=k; i++){ /// ���� ������ ��ȣ
vector<pair<ll, int> > last;
ll now = arr[i];
for(int j=0; j<n; j++){
if(now%T < off[j] || (now - now%T + off[j] < arr[i-1])) continue;
last.push_back(make_pair(now - (now%T - off[j]), j));
}
sort(last.rbegin(), last.rend()); /// ������ prefix�� ���� ����
ll addedCost[12] = {0};
ll driverCost = ((arr[i] / T) - (arr[i-1] / T)) * W;
for(int j=0; j<n; j++){
if(off[j] > arr[i]) addedCost[j] = 0;
else addedCost[j] = ((arr[i] - off[j] + T) / T - (arr[i-1] - off[j] + T) / T) * W;
}
for(int j=0; j<(1<<n); j++){
if(DP[i-1][j] >= 8e18) continue;
ll basic = DP[i-1][j] + driverCost;
for(int s=0; s<n; s++) if((j>>s)&1) basic += addedCost[s];
DP[i][j] = min(DP[i][j], basic);
int newJ = j;
for(int s=0; s<(int)last.size(); s++){
int x = last[s].second;
if(!(j&(1<<x))) continue;
newJ ^= (1<<x);
basic += cost[x] - W;
DP[i][newJ] = min(DP[i][newJ], basic);
}
}
}
for(int i=1; i<=k; i++) for(int j=0; j<(1<<n); j++){
// printf("%d %d: %lld\n", i, j, DP[i][j]);
}
for(int i=0; i<600; i++) ans = min(ans, DP[k][i]);
printf("%lld", ans);
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 340 KB | Output is correct |
| 2 | Correct | 0 ms | 340 KB | Output is correct |
| 3 | Correct | 0 ms | 212 KB | Output is correct |
| 4 | Correct | 0 ms | 340 KB | Output is correct |
| 5 | Correct | 0 ms | 340 KB | Output is correct |
| 6 | Correct | 0 ms | 340 KB | Output is correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 0 ms | 340 KB | Output is correct |
| 11 | Correct | 1 ms | 340 KB | Output is correct |
| 12 | Correct | 0 ms | 340 KB | Output is correct |
| 13 | Correct | 0 ms | 340 KB | Output is correct |
| 14 | Correct | 0 ms | 340 KB | Output is correct |
| 15 | Correct | 0 ms | 340 KB | Output is correct |
| 16 | Correct | 0 ms | 340 KB | Output is correct |
| 17 | Correct | 1 ms | 340 KB | Output is correct |
| 18 | Correct | 0 ms | 340 KB | Output is correct |
| 19 | Correct | 0 ms | 340 KB | Output is correct |
| 20 | Correct | 0 ms | 340 KB | Output is correct |
| 21 | Correct | 1 ms | 340 KB | Output is correct |
| 22 | Correct | 0 ms | 340 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 340 KB | Output is correct |
| 2 | Correct | 0 ms | 340 KB | Output is correct |
| 3 | Correct | 0 ms | 212 KB | Output is correct |
| 4 | Correct | 0 ms | 340 KB | Output is correct |
| 5 | Correct | 0 ms | 340 KB | Output is correct |
| 6 | Correct | 0 ms | 340 KB | Output is correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 0 ms | 340 KB | Output is correct |
| 11 | Correct | 1 ms | 340 KB | Output is correct |
| 12 | Correct | 0 ms | 340 KB | Output is correct |
| 13 | Correct | 0 ms | 340 KB | Output is correct |
| 14 | Correct | 0 ms | 340 KB | Output is correct |
| 15 | Correct | 0 ms | 340 KB | Output is correct |
| 16 | Correct | 0 ms | 340 KB | Output is correct |
| 17 | Correct | 1 ms | 340 KB | Output is correct |
| 18 | Correct | 0 ms | 340 KB | Output is correct |
| 19 | Correct | 0 ms | 340 KB | Output is correct |
| 20 | Correct | 0 ms | 340 KB | Output is correct |
| 21 | Correct | 1 ms | 340 KB | Output is correct |
| 22 | Correct | 0 ms | 340 KB | Output is correct |
| 23 | Runtime error | 3 ms | 1364 KB | Execution killed with signal 6 |
| 24 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 340 KB | Output is correct |
| 2 | Correct | 0 ms | 340 KB | Output is correct |
| 3 | Correct | 0 ms | 212 KB | Output is correct |
| 4 | Correct | 0 ms | 340 KB | Output is correct |
| 5 | Correct | 0 ms | 340 KB | Output is correct |
| 6 | Correct | 0 ms | 340 KB | Output is correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 0 ms | 340 KB | Output is correct |
| 11 | Correct | 1 ms | 340 KB | Output is correct |
| 12 | Correct | 0 ms | 340 KB | Output is correct |
| 13 | Correct | 0 ms | 340 KB | Output is correct |
| 14 | Correct | 0 ms | 340 KB | Output is correct |
| 15 | Correct | 0 ms | 340 KB | Output is correct |
| 16 | Correct | 0 ms | 340 KB | Output is correct |
| 17 | Correct | 1 ms | 340 KB | Output is correct |
| 18 | Correct | 0 ms | 340 KB | Output is correct |
| 19 | Correct | 0 ms | 340 KB | Output is correct |
| 20 | Correct | 0 ms | 340 KB | Output is correct |
| 21 | Correct | 1 ms | 340 KB | Output is correct |
| 22 | Correct | 0 ms | 340 KB | Output is correct |
| 23 | Runtime error | 3 ms | 1364 KB | Execution killed with signal 6 |
| 24 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 340 KB | Output is correct |
| 2 | Correct | 0 ms | 340 KB | Output is correct |
| 3 | Correct | 0 ms | 212 KB | Output is correct |
| 4 | Correct | 0 ms | 340 KB | Output is correct |
| 5 | Correct | 0 ms | 340 KB | Output is correct |
| 6 | Correct | 0 ms | 340 KB | Output is correct |
| 7 | Correct | 1 ms | 340 KB | Output is correct |
| 8 | Correct | 1 ms | 340 KB | Output is correct |
| 9 | Correct | 1 ms | 340 KB | Output is correct |
| 10 | Correct | 0 ms | 340 KB | Output is correct |
| 11 | Correct | 1 ms | 340 KB | Output is correct |
| 12 | Correct | 0 ms | 340 KB | Output is correct |
| 13 | Correct | 0 ms | 340 KB | Output is correct |
| 14 | Correct | 0 ms | 340 KB | Output is correct |
| 15 | Correct | 0 ms | 340 KB | Output is correct |
| 16 | Correct | 0 ms | 340 KB | Output is correct |
| 17 | Correct | 1 ms | 340 KB | Output is correct |
| 18 | Correct | 0 ms | 340 KB | Output is correct |
| 19 | Correct | 0 ms | 340 KB | Output is correct |
| 20 | Correct | 0 ms | 340 KB | Output is correct |
| 21 | Correct | 1 ms | 340 KB | Output is correct |
| 22 | Correct | 0 ms | 340 KB | Output is correct |
| 23 | Runtime error | 3 ms | 1364 KB | Execution killed with signal 6 |
| 24 | Halted | 0 ms | 0 KB | - |