oj.uz

Submission #117803

# Submission time Handle Problem Language Result Execution time Memory
117803 2019-06-17T08:07:08 Z 송준혁(#2882) Segway (COI19_segway) C++14
15 / 100
 12 ms 1228 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M;
int A[20202];
int B[20202];
int C[20202];
int ac[330], P[330];
int L[20202], ed;
int ans[20202];

struct Data{
    int id, t, x;
    bool operator<(const Data &r)const{
        return t > r.t;
    }
};
priority_queue<Data> PQ;

int main(){
    scanf("%d", &N);
    for (int i=1; i<=N; i++) scanf("%d %d %d", &A[i], &B[i], &C[i]);
    scanf("%d", &M);
    for (int i=1; i<=M; i++) scanf("%d", &ac[i]);
    M++;
    ac[M] = 300;
    for (int i=1; i<=N; i++){
        int k = min(100, ac[1]) * A[i];
        if (ac[1] > 100) k += min(100, ac[1]-100) * B[i];
        if (ac[1] > 200) k += min(100, ac[1]-200) * C[i];
        PQ.push((Data){i, k, 1});
    }
    int l = 0;
    while (!PQ.empty()){
        Data T = PQ.top();
        PQ.pop();
        if (l != T.t){
            for (int i=1; i<ed; i++) P[L[i]]++;
            ed = 1;
            l = T.t;
        }
        if (T.x == M) {
            ans[T.id] = T.t;
            continue;
        }

        L[ed++] = T.x;
        int nx = T.x+1;
        int d = ac[T.x] + P[T.x]%20, k = P[T.x]%20;
        while (nx < M && d > ac[nx]) nx++;
        if (nx == M && d > 300){
            ans[T.id] = T.t + k - (d - 300);
            continue;
        }
        if (d <= 100) k += min(ac[nx]-d, 100-d) * A[T.id], d = min(ac[nx], 100);
        if (d <= 200) k += min(ac[nx]-d, 200-d) * B[T.id], d = min(ac[nx], 200);
        if (d <= 300) k += min(ac[nx]-d, 300-d) * C[T.id];
        PQ.push((Data){T.id, T.t+k, nx});
    }
    for (int i=1; i<=N; i++) printf("%d\n", ans[i]);
    return 0;
}

Compilation message

segway.cpp: In function 'int main()':
segway.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
segway.cpp:24:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=N; i++) scanf("%d %d %d", &A[i], &B[i], &C[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
segway.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &M);
     ~~~~~^~~~~~~~~~
segway.cpp:26:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=1; i<=M; i++) scanf("%d", &ac[i]);
                              ~~~~~^~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 12 ms 1228 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 304 KB Output is correct
3 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 12 ms 1228 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 304 KB Output is correct
8 Incorrect 2 ms 384 KB Output isn't correct
9 Halted 0 ms 0 KB -