oj.uz

Submission #124781

# Submission time Handle Problem Language Result Execution time Memory
124781 2019-07-04T01:37:36 Z ainta Semiexpress (JOI17_semiexpress) C++17
100 / 100
 4 ms 504 KB 
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, K;
long long vA, vB, vC, T, U[3010], S[3010], res;
struct point {
    long long cur, c;
    int num;
    bool operator<(const point &p)const{
        return c<p.c;
    }
};
long long Get(long long b, long long e, int num){
    long long t = (b - U[num])*vC + S[num];
    if(t>T)return 0;
    return min((T-t)/vA + 1, e-b+1);
}
int main() {
    int i;
    scanf("%d%d%d",&n,&m,&K);
    scanf("%lld%lld%lld%lld",&vA,&vB,&vC,&T);
    for(i=1;i<=m;i++){
        scanf("%lld",&U[i]);
        if(i!=1){
            S[i] = S[i-1] + (U[i]-U[i-1])*vB;
        }
    }
    if(S[m] <= T)res++;
    priority_queue<point>PQ;
    for(i=1;i<m;i++){
        if((U[i+1] - 1 - U[i])*vA + S[i] <= T){
            res += U[i+1]-U[i];
            continue;
        }
        if(S[i]>T)continue;
        long long t = (T-S[i])/vA + 1;
        res += t;
        PQ.push({U[i]+t, Get(U[i]+t, U[i+1]-1, i), i});
    }

    for(i=m;i<K;i++){
        if(PQ.empty())break;
        point tp = PQ.top();
        PQ.pop();
        res += tp.c;
        long long x = tp.cur + tp.c;
        int num = tp.num;
        if(U[num+1] <= x)continue;
        PQ.push({x, Get(x, U[num+1]-1, num), num});
    }

    res--;
    printf("%lld\n",res);
}

Compilation message

semiexpress.cpp: In function 'int main()':
semiexpress.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&K);
     ~~~~~^~~~~~~~~~~~~~~~~~~
semiexpress.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%lld%lld",&vA,&vB,&vC,&T);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
semiexpress.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&U[i]);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 256 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 3 ms 376 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 380 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 504 KB Output is correct
28 Correct 2 ms 504 KB Output is correct
29 Correct 2 ms 376 KB Output is correct
30 Correct 2 ms 256 KB Output is correct