Submission #124781

#	Time	Username	Problem	Language	Result	Execution time	Memory
124781		ainta	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	4 ms	504 KiB

semiexpress

#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 (stderr)

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 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52