Submission #42717

#	Time	Username	Problem	Language	Result	Execution time	Memory
42717		funcsr	Shortcut (IOI16_shortcut)	C++14	38 / 100	2051 ms	1448 KiB

shortcut

#include "shortcut.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <queue>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define _1 first
#define _2 second
#define INF (1LL<<60)
struct SlideMax {
  deque<pair<int, long long> > seq;
  void add(int x, long long y) {
    while (!seq.empty() && seq.back()._2 <= y) seq.pop_back();
    seq.push_back(make_pair(x, y));
  }
  void pop(int x) {
    if (!seq.empty() && seq.front()._1 == x) seq.pop_front();
  }
  long long max() {
    if (seq.empty()) return -INF;
    /*
    long long m = -INF;
    for (auto p : seq) m = std::max(m, p._2);
    return m;
    */
    return seq.front()._2;
  }
};
int N;
long long B[1000001];

long long solve(vector<long long> W, vector<long long> ls) {
  int N = W.size();
  assert(ls.size() == N);
  B[0] = 0;
  rep(i, N) B[i+1] = B[i] + ls[i];
  long long L = B[N];
  //cout<<"solve ["; for (long long x :W) cout<<x<<",";cout<<"] ls={";for(long long b:ls)cout<<b<<",";cout<<"}, L="<<L<<"\n";
  int r = 0;
  SlideMax slide;
  long long m = -INF;
  long long base = 0;
  rep(l, N) {
    while (r < N && 2LL*(base+B[r]-B[l]) <= L) {
      slide.add(r, W[r]+base+B[r]);
      r++;
      if (r == N) {
        r = 0;
        base += L;
      }
    }
    slide.pop(l);
    m = max(m, W[l]-B[l]+slide.max());
  }
  return m;
}

long long D[1000001];
long long Rleft[1000000], Rright[1000000];
long long Dleft[1000000], Dright[1000000];

long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int C) {
  N = n;
  rep(i, N) D[i] = d[i];
  long long m = 1LL<<60;
  rep(i, N) {
    long long d = 0;
    if (i>0) d = Rleft[i-1]+l[i-1];
    Dleft[i] = max(i>0?Dleft[i-1]:0LL, d+D[i]);
    Rleft[i] = max(D[i], d);
  }
  for (int i=N-1; i>=0; i--) {
    long long d = 0;
    if (i+1<N) d = Rright[i+1]+l[i];
    Dright[i] = max(i+1<N?Dright[i+1]:0LL, d+D[i]);
    Rright[i] = max(D[i], d);
  }
  rep(x, N) for (int y=x+1; y<N; y++) {
    vector<long long> ws, bs;
    ws.pb(Rleft[x]);
    for (int i=x+1; i<y; i++) ws.pb(D[i]), bs.pb(l[i-1]);
    ws.pb(Rright[y]), bs.pb(l[y-1]);
    bs.pb(C);

    long long s = max(Dleft[x], Dright[y]);
    for (long long x : ws) s = max(x, s);
    s = max(s, solve(ws, bs));
    //cout<<"s="<<s<<"\n";
    m = min(m, s);
  }
  return m;
}

Compilation message (stderr)

In file included from /usr/include/c++/5/cassert:43:0,
                 from shortcut.cpp:5:
shortcut.cpp: In function 'long long int solve(std::vector<long long int>, std::vector<long long int>)':
shortcut.cpp:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(ls.size() == N);
                    ^

• Subtask 1: 9 / 9
• Subtask 2: 14 / 14
• Subtask 3: 8 / 8
• Subtask 4: 7 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3