Submission #1275402

---

Source Code Expand

#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#ifdef _DEBUG_
    #define debug(...) printf(__VA_ARGS__)
#else
    #define debug(...) (void)0
#endif
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;

const int MAXN=4020;
const ll INF=(ll)1e9*MAXN;
vector<PII> v1;
VI v2;
ll dp[MAXN][MAXN];
ll pre[MAXN];
deque<pair<ll,int>> deq;

int main() {
    int n;
    while(scanf("%d",&n)==1 && n) {
        int sum=0;
        v1.clear(); v2.clear();
        for(int i=0;i<n;i++) {
            int p,d;
            scanf("%d%d",&p,&d);
            sum+=d;
            if(d==1)
                v2.PB(p);
            else
                v1.PB(MP(p,d));
        }
        if(sum<2*(n-1)) {
            puts("-1");
            continue;
        }
        if(SZ(v1)==0) {
            printf("%d\n",abs(v2[1]-v2[0]));
            continue;
        }
        v1.PB(MP(-1,2));
        v2.PB(-1);
        sort(ALL(v1));
        sort(ALL(v2));
        for(PII &u:v1) u.S-=2;
        v1[1].S++; v1.back().S++;
        for(PII u:v1) debug("(%d,%d)\n",u.F,u.S);
        for(int u:v2) debug("(%d)\n",u);
        for(int i=0;i<SZ(v1);i++)
            for(int j=0;j<SZ(v2);j++)
                dp[i][j]=INF;
        dp[0][0]=0;
        for(int i=1;i<SZ(v1);i++) {
            for(int j=1;j<SZ(v2);j++) pre[j]=pre[j-1]+abs(v1[i].F-v2[j]);
            deq.clear();
            dp[i][0]=0;
            deq.PB(MP(0,0));
            for(int j=1;j<SZ(v2);j++) {
                while(SZ(deq)>=1 && 
                        deq.back().F+pre[j]-pre[deq.back().S]>=dp[i-1][j])
                    deq.pop_back();
                deq.push_back(MP(dp[i-1][j],j));
                while(deq.front().S<j-v1[i].S) deq.pop_front();
                dp[i][j]=deq.front().F+pre[j]-pre[deq.front().S];
            }
        }
        cout << dp[SZ(v1)-1][SZ(v2)-1]+(v1.back().F-v1[1].F) << '\n';
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:33:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&p,&d);
                                ^

Judge Result