Submission #1818759


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 <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<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

const ll INF = 1e17;

struct SegmentTree{
    int n, width;
    VL dat;

    void init(int x){
        n = x;
        width = 1;
        while (width < n) width *= 2;
        dat.resize(2*width-1);
        REP(i,2*width-1) dat[i] = INF;
    }

    void update(int i, ll x){
        i += width - 1;
        dat[i] = x;
        while (i > 0){
            i = (i - 1) / 2;
            dat[i] = min(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 min(vl, vr);
    }

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

ll dp[100001][101];

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

    vector<PL> p(n+1);
    REP(i,n+1) p[i] = PL(s[i], i);
    sort(ALL(p));
    VI pos(n+1);
    REP(i,n+1) pos[i] = p[i].second;

    // REP(i,n+1) cout << s[i] << " ";
    // cout << endl;
    // REP(i,n+1) cout << pos[i] << " ";
    // cout << endl;

    // VVL dp(n+1, VL(m, INF));
    // dp[0][0] = 0;
    REP(i,n) dp[i+1][0] = INF;

    SegmentTree sg1, sg2;
    sg1.init(n+1);
    sg2.init(n+1);
    REP(k,m){
        sg1.init(n+1);
        sg2.init(n+1);
        REP(i,n+1) sg1.update(i, dp[i][k] + s[i]);
        // REP(i,n+1) cout << sg1.query(i, i+1) << " ";
        // cout << endl;
        REP(i,n+1){
            // REP(j,n+1) cout << sg1.query(j, j+1) << " ";
            // cout << endl;
            // REP(j,n+1) cout << sg2.query(j, j+1) << " ";
            // cout << endl << endl;
            int p = pos[i];
            // cout << p << endl;
            dp[p][k+1] = min(sg1.query(0, p) - s[p], sg2.query(0, p) + s[p]);
            sg1.update(p, INF);
            sg2.update(p, dp[p][k] - s[p]);
        }
    }

    // cout << endl;
    // REP(k,m+1){
    //     REP(i,n+1) cout << dp[i][k] << " ";
    //     cout << endl;
    // }

    cout << dp[n][m] << endl;

    return 0;
}



Submission Info

Submission Time
Task E - 天下一合体
User TangentDay
Language C++14 (GCC 5.4.1)
Score 900
Code Size 2881 Byte
Status AC
Exec Time 617 ms
Memory 18304 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:72: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

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 31
Set Name Test Cases
Sample example0, example1, example2
All example0, example1, example2, fix0, fix1, fix2, lis0, lis1, maxrand0, maxrand1, smallrand0, smallrand1, smallrand2, smallrand3, smallrand4, smallrand5, smallrand6, smallrand7, smallrand8, smallrand9, zero0, zero1, zero2, zero3, zero4, zeromed0, zeromed1, zeromed2, zeromed3, zeromed4, zeroone0
Case Name Status Exec Time Memory
example0 AC 1 ms 256 KB
example1 AC 1 ms 256 KB
example2 AC 1 ms 256 KB
fix0 AC 584 ms 18304 KB
fix1 AC 582 ms 18304 KB
fix2 AC 579 ms 18304 KB
lis0 AC 549 ms 18304 KB
lis1 AC 552 ms 18304 KB
maxrand0 AC 602 ms 18304 KB
maxrand1 AC 617 ms 18304 KB
smallrand0 AC 1 ms 256 KB
smallrand1 AC 1 ms 256 KB
smallrand2 AC 1 ms 256 KB
smallrand3 AC 1 ms 256 KB
smallrand4 AC 1 ms 256 KB
smallrand5 AC 1 ms 256 KB
smallrand6 AC 1 ms 256 KB
smallrand7 AC 1 ms 256 KB
smallrand8 AC 1 ms 256 KB
smallrand9 AC 1 ms 256 KB
zero0 AC 588 ms 18304 KB
zero1 AC 585 ms 18304 KB
zero2 AC 580 ms 18304 KB
zero3 AC 582 ms 18304 KB
zero4 AC 582 ms 18304 KB
zeromed0 AC 5 ms 1664 KB
zeromed1 AC 5 ms 1280 KB
zeromed2 AC 2 ms 1280 KB
zeromed3 AC 5 ms 1280 KB
zeromed4 AC 7 ms 1664 KB
zeroone0 AC 2 ms 1664 KB