제출 #358511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
358511		thuanqvbn03	수열 (APIO14_sequence)	C++17	71 / 100	83 ms	131076 KiB

sequence

#include<bits/stdc++.h>
#define MAXN   100100
#define MAXK   202
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define fi   first
#define se   second
using namespace std;
class ConvexHull {
    private:
    static const int INF=(int)1e9+7;
    struct Segment {
        long long x,a,b;
        int lineID;
        Segment() {
            x=a=b=0.0;
        }
        Segment(long long _x,long long _a,long long _b,int id) {
            x=_x;a=_a;b=_b;lineID=id;
        }
        long long y(void) const {
            return (a*x+b);
        }
    };
    long long ceil(long long b,long long a) const {
        assert(a>0);
        long long x=b/a;
        FOR(i,-2,2) if ((x+i)*a>b) return (x+i);
        assert(false);
    }
    deque<Segment> dq;
    long long lastA,lastB;
    public:
    ConvexHull() {
        lastA=lastB=-INF;
    };
    void addLine(long long a,long long b,int id) {
        //printf("ADD %lld %lld\n",a,b);
        if (lastA>a || (lastA==a && lastB>=b)) return;
        lastA=a;lastB=b;
        while (!dq.empty() && dq.back().y()<=a*dq.back().x+b) dq.pop_back();
        if (dq.empty()) {
            dq.push_back(Segment(0,a,b,id));
            return;
        }
        long long x=ceil(dq.back().b-b,a-dq.back().a);
        dq.push_back(Segment(x,a,b,id));
        while (!dq.empty() && dq.back().x>=INF) dq.pop_back();
    }
    pair<long long,int> query(int x) {
        while (dq.size()>1 && dq[1].x<=x) dq.pop_front();
        return (make_pair(dq.front().a*x+dq.front().b,dq.front().lineID));
    }
};
int a[MAXN],s[MAXN],n,m;
long long dp[MAXN][MAXK];
int trc[MAXN][MAXK];
void init(void) {
    scanf("%d%d",&n,&m);m++;
    FOR(i,1,n) scanf("%d",&a[i]);
    FOR(i,1,n) s[i]=s[i-1]+a[i];
}
void optimize(void) {
    FOR(i,1,n) trc[i][1]=i;
    FOR(j,2,m) {
        ConvexHull ch;
        FOR(i,j,n) {
            ch.addLine(s[i-1],dp[i-1][j-1]-1LL*s[i-1]*s[i-1],i-1);
            pair<long long,int> tmp=ch.query(s[i]);
            dp[i][j]=tmp.fi;
            trc[i][j]=tmp.se;
//            printf("DP %d %d is %d\n",i,j,dp[i][j]);
        }
    }
}
void trace(void) {
    cout<<dp[n][m]<<endl;
    vector<int> val;
    int i=n;
    int j=m;
    while (j>0) {
        if (i<n) val.push_back(i);
        i=trc[i][j];
        j--;
    }
    sort(val.begin(),val.end());
    REP(i,val.size()) printf("%d ",val[i]); printf("\n");
}
int main(void) {
#ifdef SKY
    freopen("tmp.txt","r",stdin);
#endif // SKY
    init();
    optimize();
    trace();
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp: In function 'void trace()':
sequence.cpp:5:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    5 | #define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
      |                  ^~~
sequence.cpp:88:5: note: in expansion of macro 'REP'
   88 |     REP(i,val.size()) printf("%d ",val[i]); printf("\n");
      |     ^~~
sequence.cpp:88:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   88 |     REP(i,val.size()) printf("%d ",val[i]); printf("\n");
      |                                             ^~~~~~
sequence.cpp: In function 'void init()':
sequence.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |     scanf("%d%d",&n,&m);m++;
      |     ~~~~~^~~~~~~~~~~~~~
sequence.cpp:61:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |     FOR(i,1,n) scanf("%d",&a[i]);
      |                ~~~~~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29