Submission #386895

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
386895	2021-04-07 15:39:45	keko37	Bodyguard (JOI21_bodyguard)	C++14	0 / 100	2869 ms	296584 KiB

bodyguard

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<bits/stdc++.h>
using namespace std;
typedef long long llint;
typedef pair <llint, llint> pi;
const int MAXN = 2805;
const int MAXQ = 3000005;
int n, q;
int cost[MAXN];
pi pa[MAXN], pb[MAXN];
int upp[MAXN*3][MAXN*3], rig[MAXN*3][MAXN*3];
llint dp[MAXN*3][MAXN*3];
llint qx[MAXQ], qy[MAXQ], sol[MAXQ];
vector <llint> vx, vy;
vector <pi> ux[MAXN*3], uy[MAXN*3];
deque <pi> hull;
void precompute () {
    for (int i = 1; i <= n; i++) {
        vx.push_back(pa[i].first); vy.push_back(pa[i].second);
        vx.push_back(pb[i].first); vy.push_back(pb[i].second);
    }
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    sort(vy.begin(), vy.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

bodyguard.cpp: In function 'void precompute()':
bodyguard.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if (i + 1 < vx.size()) res = max(res, dp[i + 1][j] + rig[i][j] * (vx[i + 1] - vx[i]));
      |                 ~~~~~~^~~~~~~~~~~
bodyguard.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if (j + 1 < vy.size()) res = max(res, dp[i][j + 1] + upp[i][j] * (vy[j + 1] - vy[j]));
      |                 ~~~~~~^~~~~~~~~~~
bodyguard.cpp: In function 'void obradi(int)':
bodyguard.cpp:62:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     if (i - 1 >= 0 && i < vx.size() && x != vx[i]) ux[i].push_back({y, ind});
      |                       ~~^~~~~~~~~~~
bodyguard.cpp:63:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     if (j - 1 >= 0 && j < vy.size() && y != vy[j]) uy[j].push_back({x, ind});
      |                       ~~^~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 53