Submission #899878

#	Time	Username	Problem	Language	Result	Execution time	Memory
899878		nightfal	Wiring (IOI17_wiring)	C++14	Compilation error	0 ms	0 KiB

wiring

long long min_total_length(std::vector<int> r, std::vector<int> b) {
    int n = r.size(), m = b.size();
    vector<pair<int,int>> a(n+m);
    
    for(int i=0, j=0; i<n || j<m;)
        i==n? a[i+j++]=make_pair(j,1): j==m? a[j+i++]=make_pair(i,0): r[i]<b[j]? a[j+i++]=make_pair(i,0): a[i+j++]=make_pair(j,1);

    vector<long long> dp(n+m,LLONG_MAX);

    long long sumL=0, cntL=0, sumR=0, cntR=0, gap=0;
    int prev=-1, curr=0, optIdx=0;

    for(int i=1; i<n+m; i++) {
        if (a[i].second != a[i-1].second) {
            prev=curr; curr=i; sumR=cntR=0; sumL=0; optIdx=curr-1;
            gap= a[prev].second==0? b[a[curr].first]-r[a[curr-1].first]: r[a[curr].first]-b[a[curr-1].first];
        }

        if (prev==-1) continue;

        sumR += a[curr].second==0? r[a[i].first]-r[a[curr].first]:b[a[i].first]-b[a[curr].first];
        cntR++;

        for(int j=optIdx; j>=prev; j--) {
            cntL=curr-j; 
            sumL += a[prev].second==0? r[a[curr-1].first]-r[a[j].first]:b[a[curr-1].first]-b[a[j].first]; 
            long long temp = sumL + sumR + max(cntL,cntR)*gap;
            if (j==0) {dp[i] = min(dp[i],temp); optIdx = 0;}
            else {
                long long minDP = min(dp[j-1],dp[j]);        
                if (minDP == LLONG_MAX) continue;
                else temp += minDP;                    
                if (dp[i]>temp) {dp[i]=temp;optIdx=j;}
                else break;
            }
        }
        for(int k=max(optIdx-1,prev); k<=optIdx; k++)
            sumL -= a[prev].second==0? r[a[curr-1].first]-r[a[k].first]:b[a[curr-1].first]-b[a[k].first]; 
    }
    return dp[n+m-1];
}

Compilation message (stderr)

wiring.cpp:1:33: error: 'vector' is not a member of 'std'
    1 | long long min_total_length(std::vector<int> r, std::vector<int> b) {
      |                                 ^~~~~~
wiring.cpp:1:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
  +++ |+#include <vector>
    1 | long long min_total_length(std::vector<int> r, std::vector<int> b) {
wiring.cpp:1:40: error: expected primary-expression before 'int'
    1 | long long min_total_length(std::vector<int> r, std::vector<int> b) {
      |                                        ^~~
wiring.cpp:1:53: error: 'vector' is not a member of 'std'
    1 | long long min_total_length(std::vector<int> r, std::vector<int> b) {
      |                                                     ^~~~~~
wiring.cpp:1:53: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
wiring.cpp:1:60: error: expected primary-expression before 'int'
    1 | long long min_total_length(std::vector<int> r, std::vector<int> b) {
      |                                                            ^~~
wiring.cpp:1:66: error: expression list treated as compound expression in initializer [-fpermissive]
    1 | long long min_total_length(std::vector<int> r, std::vector<int> b) {
      |                                                                  ^