Submission #2337436

---

Source Code Expand

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long int64;
const int64 INF = 1LL << 58;
 
int64 MinimumCost(vector< int > &A, vector< int > &B)
{
  vector< int > near(B.size());
  int tail = 0;
  for(int i = 0; i < B.size(); i++) {
    while(tail < A.size() && A[tail] < B[i]) ++tail;
    near[i] = tail;
  }
  int sz = (int) B.size() * 2 + 1;
  vector< int64 > dp(sz, 0);
  for(int i = 0; i < B.size(); i++) {
    const int diff = near[i] - (i == 0 ? 0 : near[i - 1]);
    for(int j = 0; j < sz; j++) dp[j] = dp[min(j + diff, sz - 1)];
    vector< int64 > nxt(sz, INF);
    for(int j = 0; j < sz - 1; j++) {
      const int k = near[i] - (int) B.size() + j;
      nxt[j + 1] = min(nxt[j + 1], nxt[j]);
      if(k < 0 || k >= A.size()) continue;
      nxt[j + 1] = min(nxt[j + 1], dp[j] + abs(B[i] - A[k]));
    }
    dp.swap(nxt);
  }
  if(dp.back() == INF) return (-1);
  return (dp.back());
}
 
int main()
{
  int N, P[4000], D[4000];
 
  while(scanf("%d", &N), N) {
    if(N == 2) {
      int a, b, c, d;
      scanf("%d %d %d %d", &a, &b, &c, &d);
      printf("%d\n", abs(a - c));
      continue;
    }
    vector< int > latte, malta;
    for(int i = 0; i < N; i++) {
      scanf("%d %d", &P[i], &D[i]);
      if(D[i] == 1) latte.push_back(i);
      else malta.push_back(i);
    }
 
    sort(begin(latte), end(latte), [&](int a, int b) -> bool
    {
      return (P[a] < P[b]);
    });
    sort(begin(malta), end(malta), [&](int a, int b) -> bool
    {
      return (P[a] < P[b]);
    });
 
    for(int i = 1; i < malta.size(); i++) --D[malta[i]];
    for(int i = 0; i + 1 < malta.size(); i++) --D[malta[i]];
 
    vector< int > beet, vs;
    for(int i : malta) while(D[i]--) beet.push_back(P[i]);
    for(int i : latte) vs.push_back(P[i]);
    if(vs.size() > beet.size()) puts("-1");
    else printf("%lld\n", MinimumCost(beet, vs) + P[malta.back()] - P[malta.front()]);
  }
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:38:3: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   while(scanf("%d", &N), N) {
   ^
./Main.cpp:41:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d %d", &a, &b, &c, &d);
                                           ^
./Main.cpp:47:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &P[i], &D[i]);
                                   ^

Judge Result