Submission #39327

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
39327	2018-01-11 09:09:31	14kg	Robots (IOI13_robots)	C++11	100 / 100	2209 ms	22492 KiB

robots

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "robots.h"
#include <algorithm>
#include <queue>
#include <functional>
#define N 1000001
#define max2(x,y) (x>y?x:y)
using namespace std;
int len_a, len_b, len_toy, pass_len;
int A[50001], B[500010], pass[N];
pair<int, int> toy[N];
priority_queue<int,vector<int>,greater<int> > Q;
bool Can(int max_size) {
  int k = len_a;
  long long r_size = 0;
  
  pass_len = 0;
  while (!Q.empty()) Q.pop();
  for (int i = len_toy; i >= 1; i--) {
    while (toy[i].first <= A[k]) k--, r_size += (long long)max_size;
    r_size--, Q.push(toy[i].second);
    if (r_size < 0) pass[++pass_len] = Q.top(), Q.pop(), r_size++;
  }
  sort(pass + 1, pass + pass_len + 1); 
  k = len_b + 1, r_size = 0;
  for (int i = pass_len; i >= 1; i--) {
    if (!r_size) k--, r_size = (long long)max_size;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10