Submission #2019301

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

struct SegmentTree{
    const ll INF = 1e9;
    int n, width;
    VL dat;

    void init(int x){
        n = x;
        width = 1;
        while (width < n) width *= 2;
        dat.assign(2*width-1, -INF);
    }

    void update(int i, ll x){
        i += width - 1;
        dat[i] = x;
        while (i > 0){
            i = (i - 1) / 2;
            dat[i] = max(dat[i*2+1], dat[i*2+2]);
        }
    }

    ll query(int a, int b, int k, int l, int r){
        if (r <= a || b <= l) return -INF;
        if (a <= l && r <= b) return dat[k];
        ll vl = query(a, b, k*2+1, l, (l+r)/2);
        ll vr = query(a, b, k*2+2, (l+r)/2, r);
        return max(vl, vr);
    }

    // [l, r)
    ll query(int l, int r){
        return query(l, r, 0, 0, width);
    }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    VL a(n);
    REP(i,n) scanf("%lld", &a[i]);

    SegmentTree seg[2];
    seg[0].init(n);
    seg[1].init(n);
    REP(i,n) seg[0].update(i, a[i]);

    REP(x,k-1){
        int now = x % 2;
        int next = now ^ 1;

        FOR(i,1,n-1){
            seg[next].update(i, seg[now].query(max(0, i - m), i) + a[i] * (x + 2));
        }
    }

    cout << seg[(k-1)%2].query(0, n) << endl;
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:69:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     REP(i,n) scanf("%lld", &a[i]);
                                  ^

Judge Result