Submission #58751

#	Time	Username	Problem	Language	Result	Execution time	Memory
58751		TAMREF	오렌지 출하 (JOI16_ho_t1)	C++11	100 / 100	146 ms	5868 KiB

2016_ho_t1

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mx = 2e5, mlgx = log2(mx)+1;
const ll inf = 1e16;

ll D[mx];
ll A[mx];
int n, m;
ll k;

ll tmax[mlgx][mx];
ll tmin[mlgx][mx];
int tlg[mx];

inline ll rMq_rmq(int s, int e){
    int lev = tlg[e-s+1];
    ll RMQ = max(tmax[lev][s], tmax[lev][e-(1<<lev)+1]);
    ll rmq = min(tmin[lev][s], tmin[lev][e-(1<<lev)+1]);
    //printf("RMQ,rmq(%d,%d) = (%lld,%lld)\n",s,e,RMQ,rmq);
    //printf("probe 1 = %d, probe 2 = %d\n",s,e-(1<<lev));
    return RMQ-rmq;
}

void input(){
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }
    for(int i = 1; i <= n; i++){
        int j = 0;
        while((1<<j+1) <= i) ++j;
        tlg[i] = j;
    }
    copy(A+1,A+n+1,tmax[0]+1);
    copy(A+1,A+n+1,tmin[0]+1);

    for(int l = 1, b = 1; (1<<l) <= n; l++, b <<= 1){
        for(int i = 0; i + b <= n; i++){
            tmax[l][i] = max(tmax[l-1][i], tmax[l-1][i+b]);
            tmin[l][i] = min(tmin[l-1][i], tmin[l-1][i+b]);
        }
    }
}

void dp(){
    for(int i = 1; i <= n; i++){
        D[i] = inf;
        ll tmp;
        for(int j = max(0,i-m); j < i; j++){
            tmp = k + rMq_rmq(j+1,i) * (i - j);
            D[i] = min(D[i], D[j] + tmp);
        }
    }
    cout << D[n] << '\n';
}

void debug(){
    puts("tmax");
    for(int l = 0; (1<<l) <= n; l++){
        for(int i = 0; i <= n; i++){
            printf("%lld ",tmax[l][i]);
        }
        puts("");
    }
    puts("tmin");
    for(int l = 0; (1<<l) <= n; l++){
        for(int i = 0; i <= n; i++){
            printf("%lld ",tmin[l][i]);
        }
        puts("");
    }
    puts("dp");
    for(int i = 1; i <= n; i++){
        printf("%lld ",D[i]);
    }
    puts("");
}

int main(){
    //freopen("sample.txt","rt",stdin);
    ios_base::sync_with_stdio(false);cin.tie(0);
    input();
    dp();
    //debug();
}

Compilation message (stderr)

2016_ho_t1.cpp: In function 'void input()':
2016_ho_t1.cpp:33:20: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
         while((1<<j+1) <= i) ++j;
                   ~^~

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50
• Subtask 3: 30 / 30