| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 595928 |
2022-07-14T08:09:48 Z |
조영욱(#8444) |
Bodyguard (JOI21_bodyguard) |
C++17 |
|
25000 ms |
281604 KB |
#include <bits/stdc++.h>
using namespace std;
int n,q;
vector<long long> px;
vector<long long> py;
typedef pair<long long,long long> P;
typedef pair<P,P> PP;
typedef pair<PP,int> PPi;
vector<PPi> v;
int arr[5600][5600][2]; //0:x�� 1:y��
long long dp[5600][5600];
int main() {
scanf("%d %d",&n,&q);
for(int i=0;i<n;i++) {
long long t,a,b,c;
scanf("%lld %lld %lld %lld",&t,&a,&b,&c);
long long x1=t+a;
long long y1=t-a;
long long x2=t+abs(b-a)+b;
long long y2=t+abs(b-a)-b;
c/=2;
v.push_back(PPi(PP(P(x1,y1),P(x2,y2)),c));
px.push_back(x1);
px.push_back(x2);
py.push_back(y1);
py.push_back(y2);
}
sort(px.begin(),px.end());
px.erase(unique(px.begin(),px.end()),px.end());
sort(py.begin(),py.end());
py.erase(unique(py.begin(),py.end()),py.end());
for(int i=0;i<n;i++) {
v[i].first.first.first=lower_bound(px.begin(),px.end(),v[i].first.first.first)-px.begin();
v[i].first.first.second=lower_bound(py.begin(),py.end(),v[i].first.first.second)-py.begin();
v[i].first.second.first=lower_bound(px.begin(),px.end(),v[i].first.second.first)-px.begin();
v[i].first.second.second=lower_bound(py.begin(),py.end(),v[i].first.second.second)-py.begin();
if (v[i].first.first.second==v[i].first.second.second) {
for(int j=v[i].first.first.first;j<v[i].first.second.first;j++) {
arr[j][v[i].first.first.second][0]=max(arr[j][v[i].first.first.second][0],v[i].second);
}
}
else {
for(int j=v[i].first.first.second;j<v[i].first.second.second;j++) {
arr[v[i].first.first.first][j][1]=max(arr[v[i].first.first.first][j][1],v[i].second);
}
}
}
for(int i=px.size()-1;i>=0;i--) {
for(int j=py.size()-1;j>=0;j--) {
if (i+1<px.size()) {
dp[i][j]=max(dp[i][j],dp[i+1][j]+1LL*arr[i][j][0]*(px[i+1]-px[i]));
}
if (j+1<py.size()) {
dp[i][j]=max(dp[i][j],dp[i][j+1]+1LL*arr[i][j][1]*(py[j+1]-py[j]));
}
}
}
for(int i=0;i<q;i++) {
int t,pos;
scanf("%d %d",&t,&pos);
int x=t+pos;
int y=t-pos;
int xind=lower_bound(px.begin(),px.end(),x)-px.begin();
int yind=lower_bound(py.begin(),py.end(),y)-py.begin();
if (xind==px.size()||yind==py.size()) {
printf("0\n");
continue;
}
long long ret=dp[xind][yind];
if (true) {
if (xind!=0) {
for(int j=yind;j<py.size();j++) {
ret=max(ret,1LL*arr[xind-1][j][0]*(px[xind]-x)+dp[xind][j]);
}
}
if (yind!=0) {
for(int j=xind;j<px.size();j++) {
ret=max(ret,1LL*arr[j][yind-1][1]*(py[yind]-y)+dp[j][yind]);
}
}
//pl=max(pl,arr[xind-1][yind][0]*(px[xind]-x));
//pl=max(pl,arr[xind][yind-1][1]*(py[yind]-y));
}
printf("%lld\n",ret);
}
return 0;
}
Compilation message
bodyguard.cpp: In function 'int main()':
bodyguard.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if (i+1<px.size()) {
| ~~~^~~~~~~~~~
bodyguard.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | if (j+1<py.size()) {
| ~~~^~~~~~~~~~
bodyguard.cpp:67:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | if (xind==px.size()||yind==py.size()) {
| ~~~~^~~~~~~~~~~
bodyguard.cpp:67:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | if (xind==px.size()||yind==py.size()) {
| ~~~~^~~~~~~~~~~
bodyguard.cpp:74:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int j=yind;j<py.size();j++) {
| ~^~~~~~~~~~
bodyguard.cpp:79:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int j=xind;j<px.size();j++) {
| ~^~~~~~~~~~
bodyguard.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
15 | scanf("%d %d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~~
bodyguard.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%lld %lld %lld %lld",&t,&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%d %d",&t,&pos);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
25088 ms |
149628 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
281 ms |
279976 KB |
Output is correct |
| 2 |
Correct |
278 ms |
278088 KB |
Output is correct |
| 3 |
Correct |
259 ms |
275872 KB |
Output is correct |
| 4 |
Correct |
3 ms |
852 KB |
Output is correct |
| 5 |
Correct |
248 ms |
218600 KB |
Output is correct |
| 6 |
Correct |
228 ms |
195592 KB |
Output is correct |
| 7 |
Correct |
266 ms |
218464 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
281 ms |
279976 KB |
Output is correct |
| 2 |
Correct |
278 ms |
278088 KB |
Output is correct |
| 3 |
Correct |
259 ms |
275872 KB |
Output is correct |
| 4 |
Correct |
3 ms |
852 KB |
Output is correct |
| 5 |
Correct |
248 ms |
218600 KB |
Output is correct |
| 6 |
Correct |
228 ms |
195592 KB |
Output is correct |
| 7 |
Correct |
266 ms |
218464 KB |
Output is correct |
| 8 |
Correct |
429 ms |
280124 KB |
Output is correct |
| 9 |
Correct |
417 ms |
278040 KB |
Output is correct |
| 10 |
Correct |
247 ms |
274048 KB |
Output is correct |
| 11 |
Correct |
9 ms |
992 KB |
Output is correct |
| 12 |
Correct |
400 ms |
218700 KB |
Output is correct |
| 13 |
Correct |
413 ms |
195776 KB |
Output is correct |
| 14 |
Correct |
256 ms |
218732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
281 ms |
279976 KB |
Output is correct |
| 2 |
Correct |
278 ms |
278088 KB |
Output is correct |
| 3 |
Correct |
259 ms |
275872 KB |
Output is correct |
| 4 |
Correct |
3 ms |
852 KB |
Output is correct |
| 5 |
Correct |
248 ms |
218600 KB |
Output is correct |
| 6 |
Correct |
228 ms |
195592 KB |
Output is correct |
| 7 |
Correct |
266 ms |
218464 KB |
Output is correct |
| 8 |
Correct |
429 ms |
280124 KB |
Output is correct |
| 9 |
Correct |
417 ms |
278040 KB |
Output is correct |
| 10 |
Correct |
247 ms |
274048 KB |
Output is correct |
| 11 |
Correct |
9 ms |
992 KB |
Output is correct |
| 12 |
Correct |
400 ms |
218700 KB |
Output is correct |
| 13 |
Correct |
413 ms |
195776 KB |
Output is correct |
| 14 |
Correct |
256 ms |
218732 KB |
Output is correct |
| 15 |
Correct |
2422 ms |
281036 KB |
Output is correct |
| 16 |
Correct |
2440 ms |
281604 KB |
Output is correct |
| 17 |
Correct |
613 ms |
277828 KB |
Output is correct |
| 18 |
Correct |
40 ms |
1956 KB |
Output is correct |
| 19 |
Correct |
2052 ms |
219752 KB |
Output is correct |
| 20 |
Correct |
3139 ms |
196812 KB |
Output is correct |
| 21 |
Correct |
283 ms |
219656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
25088 ms |
149628 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
