Submission #211677

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
211677	2020-03-21 00:34:25	anonymous	Robots (IOI13_robots)	C++14	100 / 100	1785 ms	22892 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<queue>
#include<utility>
#include<algorithm>
#define MAXT 1000005
#define MAXR 50005
using namespace std;
pair<int,int> Toy[MAXT];
priority_queue<int> PQ; //from big to small
int A, B, T, Weak[MAXR], Small[MAXR]; //weak size, small size
bool can(int k) {
    int pt = 0;
    while (PQ.size()) {PQ.pop();}
    for (int i=0; i<A; i++) {
        while (pt < T && Toy[pt].first < Weak[i]) {
            PQ.push(Toy[pt].second), pt++;
        }
        for (int j=0; j<k && PQ.size(); j++) {PQ.pop();}
    }
    for (int i=pt; i<T; i++) {
        PQ.push(Toy[i].second);
    }
    for (int i=B-1; i>=0; i--) {
        for (int j=0; j<k; j++) {
            if (PQ.size() && PQ.top() < Small[i]) {PQ.pop();}
            else {break;}
        }
    }
    return(PQ.empty());
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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