oj.uz

Submission #600655

# Submission time Handle Problem Language Result Execution time Memory
600655 2022-07-21T06:41:52 Z 반딧불(#8467) Long Distance Coach (JOI17_coach) C++17
0 / 100
 1 ms 340 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]);
    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;
            assert(now - (now%T - off[j]) > arr[i-1]);
            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

coach.cpp: In function 'int main()':
coach.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%lld %d %d %lld %lld", &X, &k, &n, &W, &T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:16:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     for(int i=1; i<=k; i++) scanf("%lld", &arr[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~
coach.cpp:18:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     for(int i=0; i<n; i++) scanf("%lld %lld", &off[i], &cost[i]);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 260 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 260 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 260 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 260 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Incorrect 1 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -