oj.uz

Submission #42715

# Submission time Handle Problem Language Result Execution time Memory
42715 2018-03-03T04:26:01 Z funcsr Shortcut (IOI16_shortcut) C++14
0 / 100
 2 ms 560 KB 
#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
struct SlideMax {
  deque<pair<int, long long> > seq;
  void add(int x, long long y) {
    seq.pb(P(x, y));
  }
  void pop(int x) {
    if (!seq.empty() && seq.front()._1 == x) seq.pop_front();
  }
  long long max() {
    if (seq.empty()) return 0;
    long long m = 0;
    for (auto p : seq) m = std::max(m, p._2);
    return m;
  }
};
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 = 0;
  rep(l, N) {
    slide.pop(l);
    while (r < N && 2LL*(B[r]-B[l]) <= L) {
      slide.add(r, W[r]+B[r]);
      r++;
    }
    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;
    long long cur = 0;
    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));
    reverse(ws.begin()+1, ws.end()), reverse(all(bs));
    s = max(s, solve(ws, bs));
    //cout<<"s="<<s<<"\n";
    m = min(m, s);
  }
  return m;
}

Compilation message

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:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(ls.size() == N);
                    ^
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:75:15: warning: unused variable 'cur' [-Wunused-variable]
     long long cur = 0;
               ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 560 KB n = 4, 21 is a correct answer
4 Correct 2 ms 560 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 560 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 560 KB n = 4, 21 is a correct answer
4 Correct 2 ms 560 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 560 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 560 KB n = 4, 21 is a correct answer
4 Correct 2 ms 560 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 560 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 560 KB n = 4, 21 is a correct answer
4 Correct 2 ms 560 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 560 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 560 KB n = 4, 21 is a correct answer
4 Correct 2 ms 560 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 560 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 560 KB n = 4, 21 is a correct answer
4 Correct 2 ms 560 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 560 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 560 KB n = 4, 21 is a correct answer
4 Correct 2 ms 560 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 560 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 4, 80 is a correct answer
2 Correct 2 ms 484 KB n = 9, 110 is a correct answer
3 Correct 2 ms 560 KB n = 4, 21 is a correct answer
4 Correct 2 ms 560 KB n = 3, 4 is a correct answer
5 Incorrect 1 ms 560 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -