Submission #1095192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095192		phong	오렌지 출하 (JOI16_ho_t1)	C++17	100 / 100	182 ms	6488 KiB

2016_ho_t1

#include<bits/stdc++.h>
#define ll long long
#define int long long
const int nmax = 2e4 + 5, N = 2e6;
const ll oo = 1e12 + 5, base = 3001;
const int lg = 17,mod = 998244353;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, m, k, a[nmax];
int ma[nmax][lg + 1], mi[nmax][lg + 1];
int f[nmax];

int calc(int i, int j, int idx){
    if(idx == 0){
        int k = __lg(j - i + 1);
        return min(mi[i][k], mi[j - (1 << k) + 1][k]);
    }
    else{
        int k = __lg(j - i + 1);
        return max(ma[i][k], ma[j - (1 <<k) + 1][k]);
    }
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("FRIENDS.inp", "r", stdin);
//    freopen("FRIENDS.out", "w", stdout);
    cin >> n >> m >> k;;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i){
        mi[i][0] = a[i];
        ma[i][0] = a[i];
    }
    for(int j = 1; j <= lg; ++j){
        for(int i = 1; i + (1 << j) - 1 <= n; ++i){
            mi[i][j] = min(mi[i][j - 1], mi[i + (1 << (j - 1))][j - 1]);
            ma[i][j] = max(ma[i][j - 1], ma[i + (1 << (j - 1))][j - 1]);
        }
    }
    for(int i = 1; i <= n; ++i){
        f[i] = 1e18;
        for(int j = max(1ll, i - m + 1); j <= i; ++j){
            int cost = (i - j + 1) * (calc(j, i, 1) - calc(j, i, 0)) + k;
            f[i] = min(f[i], f[j - 1] + cost);
        }
    }
//    int pos = 1;
//    while(pos <= n){
//        int x;
//        cin >> x;
//        int i = pos + x - 1;
//        int j = pos;
//        int cost = (i - j + 1) * (calc(j, i, 1) - calc(j, i, 0)) + k;
//        f[n] += cost;
//        pos = i + 1;
//    }
    cout << f[n];
}
/*
16 4 12
3
10
13
10
19
9
12
16
11
2
19
9
13
2
13
19

*/

Compilation message (stderr)

2016_ho_t1.cpp:28:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   28 | main(){
      | ^~~~

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