| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 595888 |
2022-07-14T07:53:07 Z |
조영욱(#8444) |
Bodyguard (JOI21_bodyguard) |
C++17 |
|
2591 ms |
730856 KB |
#include <bits/stdc++.h>
using namespace std;
int n,q;
vector<int> px;
vector<int> py;
typedef pair<int,int> P;
typedef pair<P,P> PP;
typedef pair<PP,int> PPi;
vector<PPi> v;
long long arr[6600][6600][2]; //0:x�� 1:y��
long long dp[6600][6600];
int main() {
scanf("%d %d",&n,&q);
for(int i=0;i<n;i++) {
int t,a,b,c;
scanf("%d %d %d %d",&t,&a,&b,&c);
int x1=t+a;
int y1=t-a;
int x2=t+abs(b-a)+b;
int 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);
}
for(int i=0;i<=6000;i++) {
px.push_back(i);
}
for(int i=-3000;i<=3000;i++) {
py.push_back(i);
}
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],(long long)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],(long long)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]+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]+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 (false) {
if (xind!=0) {
for(int j=yind;j<py.size();j++) {
ret=max(ret,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,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:58:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | if (i+1<px.size()) {
| ~~~^~~~~~~~~~
bodyguard.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | if (j+1<py.size()) {
| ~~~^~~~~~~~~~
bodyguard.cpp:73:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if (xind==px.size()||yind==py.size()) {
| ~~~~^~~~~~~~~~~
bodyguard.cpp:73:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if (xind==px.size()||yind==py.size()) {
| ~~~~^~~~~~~~~~~
bodyguard.cpp:80:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int j=yind;j<py.size();j++) {
| ~^~~~~~~~~~
bodyguard.cpp:85:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | 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("%d %d %d %d",&t,&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguard.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
68 | scanf("%d %d",&t,&pos);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2312 ms |
722856 KB |
Output is correct |
| 2 |
Correct |
2591 ms |
730856 KB |
Output is correct |
| 3 |
Correct |
2233 ms |
415520 KB |
Output is correct |
| 4 |
Correct |
2097 ms |
352732 KB |
Output is correct |
| 5 |
Runtime error |
22 ms |
15572 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
17 ms |
852 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2312 ms |
722856 KB |
Output is correct |
| 2 |
Correct |
2591 ms |
730856 KB |
Output is correct |
| 3 |
Correct |
2233 ms |
415520 KB |
Output is correct |
| 4 |
Correct |
2097 ms |
352732 KB |
Output is correct |
| 5 |
Runtime error |
22 ms |
15572 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
