oj.uz

Submission #1036577

# Submission time Handle Problem Language Result Execution time Memory
1036577 2024-07-27T14:22:20 Z hotboy2703 Bodyguard (JOI21_bodyguard) C++17
28 / 100
 2029 ms 2097152 KB 
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
ll n,q;
const ll MAXN = 2827;
const ll MAX_Q = 3e6+100;
const ll INF = 1e18;
ll V[MAXN],A[MAXN],B[MAXN],C[MAXN],D[MAXN];

ll P[MAX_Q],X[MAX_Q];

ll ans[MAX_Q];
struct query{
	ll r,c,id;
};
query all[MAX_Q];
ll inter(pll x1,pll x2){
	swap(x1,x2);
	if (x1.fi==x2.fi)return (x1.se < x2.se ? -INF : INF);
	return (x2.se-x1.se)/(x1.fi-x2.fi);
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(nullptr);
	cin>>n>>q;
	for (ll i = 1;i <= n;i ++){
		cin>>C[i]>>A[i]>>B[i]>>V[i];
		D[i] = C[i] + abs(A[i]-B[i]);
	}
	for (ll i = 1;i <= q;i ++){
		cin>>P[i]>>X[i];
	}
	vector <ll> row,col;
	for (ll i = 1;i <= n;i ++){
		row.push_back(C[i]+A[i]); 
		row.push_back(D[i]+B[i]);
		col.push_back(C[i]-A[i]);
		col.push_back(D[i]-B[i]);
	}
	for (ll i = 1;i <= q;i ++){
		row.push_back(P[i]+X[i]); 
		col.push_back(P[i]-X[i]);
	}
	sort(row.begin(),row.end());
	row.resize(unique(row.begin(),row.end())-row.begin());
	sort(col.begin(),col.end());
	col.resize(unique(col.begin(),col.end())-col.begin());
	vector <vector <ll> > ar,ac,dp;
	dp=ar=ac=vector<vector <ll> > (sz(row),vector <ll>(sz(col)));
	for (ll i = 1;i <= n;i ++){
		if (A[i] > B[i]){
			ll x = lower_bound(row.begin(),row.end(),C[i]+A[i])-row.begin();
			for (ll j = 0;j < sz(col);j ++){
				if (C[i] - A[i] < col[j] && D[i] - B[i] >= col[j]){
					ar[x][j] = max(V[i],ar[x][j]);
				}
			}
		}
		else{
			ll y = lower_bound(col.begin(),col.end(),C[i]-A[i])-col.begin();
			for (ll j = 0;j < sz(row);j ++){
				if (C[i] + A[i] < row[j] && row[j] <= D[i] + B[i]){
					ac[j][y] = max(ac[j][y],V[i]);
				}
			}
		}
	}
	for (ll i = sz(row)-1; i >= 0; i --){
		for (ll j = sz(col)-1; j >= 0; j --){
			if (i)dp[i-1][j] = max(dp[i-1][j],dp[i][j] + ac[i][j] * (row[i] - row[i-1]));
			if (j)dp[i][j-1] = max(dp[i][j-1],dp[i][j] + ar[i][j] * (col[j] - col[j-1]));
		}
	}
	for (ll i = 1;i <= q;i ++){
		cout<<dp[lower_bound(row.begin(),row.end(),P[i]+X[i])-row.begin()][lower_bound(col.begin(),col.end(),P[i]-X[i])-col.begin()]/2<<'\n';
	}
	// for (ll i = 0;i < sz(row);i ++){
	// 	for (ll j = 0;j < sz(col);j ++){
	// 		cout<<"DP "<<row[i]<<' '<<col[j]<<" : "<<dp[i][j]<<endl;
	// 	}
	// }
	for (ll i = 1;i <= q;i ++){
		all[i] = {P[i]+X[i],P[i]-X[i],i};
		// cout<<P[i]+X[i]<<' '<<P[i]-X[i]<<endl;
	}
	// cout<<row[5]<<' '<<col[3]<<' '<<ar[5][3]<<' '<<ac[5][3]<<endl;
	// for (ll i = 1;i <= q;i ++)cout<<ans[i]/2<<'\n';
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1958 ms 1145076 KB Output is correct
2 Correct 1938 ms 1141268 KB Output is correct
3 Correct 1958 ms 1068284 KB Output is correct
4 Correct 1923 ms 1060036 KB Output is correct
5 Correct 2029 ms 1450236 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 415664 KB Output is correct
2 Correct 248 ms 415736 KB Output is correct
3 Correct 227 ms 409792 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 250 ms 415628 KB Output is correct
6 Correct 223 ms 415572 KB Output is correct
7 Correct 277 ms 414792 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 415664 KB Output is correct
2 Correct 248 ms 415736 KB Output is correct
3 Correct 227 ms 409792 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 250 ms 415628 KB Output is correct
6 Correct 223 ms 415572 KB Output is correct
7 Correct 277 ms 414792 KB Output is correct
8 Correct 680 ms 1219292 KB Output is correct
9 Correct 682 ms 1219412 KB Output is correct
10 Correct 634 ms 1212500 KB Output is correct
11 Correct 60 ms 95548 KB Output is correct
12 Correct 458 ms 712276 KB Output is correct
13 Correct 656 ms 1219156 KB Output is correct
14 Correct 661 ms 1219136 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 415664 KB Output is correct
2 Correct 248 ms 415736 KB Output is correct
3 Correct 227 ms 409792 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 250 ms 415628 KB Output is correct
6 Correct 223 ms 415572 KB Output is correct
7 Correct 277 ms 414792 KB Output is correct
8 Correct 680 ms 1219292 KB Output is correct
9 Correct 682 ms 1219412 KB Output is correct
10 Correct 634 ms 1212500 KB Output is correct
11 Correct 60 ms 95548 KB Output is correct
12 Correct 458 ms 712276 KB Output is correct
13 Correct 656 ms 1219156 KB Output is correct
14 Correct 661 ms 1219136 KB Output is correct
15 Runtime error 804 ms 2097152 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1958 ms 1145076 KB Output is correct
2 Correct 1938 ms 1141268 KB Output is correct
3 Correct 1958 ms 1068284 KB Output is correct
4 Correct 1923 ms 1060036 KB Output is correct
5 Correct 2029 ms 1450236 KB Output is correct
6 Correct 248 ms 415664 KB Output is correct
7 Correct 248 ms 415736 KB Output is correct
8 Correct 227 ms 409792 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 250 ms 415628 KB Output is correct
11 Correct 223 ms 415572 KB Output is correct
12 Correct 277 ms 414792 KB Output is correct
13 Correct 680 ms 1219292 KB Output is correct
14 Correct 682 ms 1219412 KB Output is correct
15 Correct 634 ms 1212500 KB Output is correct
16 Correct 60 ms 95548 KB Output is correct
17 Correct 458 ms 712276 KB Output is correct
18 Correct 656 ms 1219156 KB Output is correct
19 Correct 661 ms 1219136 KB Output is correct
20 Runtime error 804 ms 2097152 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -