oj.uz

답안 #600696

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
600696 2022-07-21T07:08:05 Z 반딧불(#8467) Long Distance Coach (JOI17_coach) C++17
16 / 100
 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

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:19:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     for(int i=0; i<n; i++) scanf("%lld %lld", &off[i], &cost[i]);
      |                            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 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

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 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 -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 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 -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 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 -