oj.uz

Submission #577481

# Submission time Handle Problem Language Result Execution time Memory
577481 2022-06-14T20:25:05 Z inksamurai Bodyguard (JOI21_bodyguard) C++17
7 / 100
 25000 ms 1658968 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3MJnHrA ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

using T=pair<int,pair<pii,pii>>;

signed main(){
_3MJnHrA;
	int n,q;
	cin>>n>>q;

	vec(T) a(n);
	rep(i,n){
		int _t,_l,_r,_c;
		cin>>_t>>_l>>_r>>_c;
		pii s={_t,_l};
		pii t={_t+abs(_r-_l),_r};
		s={s.fi-s.se,s.fi+s.se};
		t={t.fi-t.se,t.fi+t.se};
		a[i]=T(_c,{s,t});
	}

	vi xys;
	rep(i,n){
		pii s=a[i].se.fi,t=a[i].se.se;
		// print(s.fi,s.se,t.fi,t.se);
		xys.pb(s.fi);
		xys.pb(s.se);
		xys.pb(t.fi);
		xys.pb(t.se);
	}
	sort(xys.begin(), xys.end());
	xys.erase(unique(xys.begin(), xys.end()),xys.end());

	auto ced=[&](int x){
		return (int)(lower_bound(xys.begin(), xys.end(),x)-xys.begin());
	};

	int _n=sz(xys);
	vec(vi) movex(_n,vi(_n)),movey;
	movey=movex;
	{
		rep(i,n){
			int cosu=a[i].fi;
			pii s=a[i].se.fi,t=a[i].se.se;
			int type=s.fi==t.fi;
			s.fi=ced(s.fi);
			s.se=ced(s.se);
			t.fi=ced(t.fi);
			t.se=ced(t.se);
			// print(s.fi,s.se,t.fi,t.se);
			if(type){
				rng(j,s.se,t.se){
					movey[s.fi][j]=cosu;
				}
			}else{
				rng(j,s.fi,t.fi){
					movex[j][s.se]=cosu;
				}
			}
		}
	}

	vec(vi) dp(_n,vi(_n));
	per(i,_n){
		per(j,_n){
			if(i+1<_n){
				dp[i][j]=max(dp[i][j],dp[i+1][j]+(xys[i+1]-xys[i])*movex[i][j]);
			}
			if(j+1<_n){
				dp[i][j]=max(dp[i][j],dp[i][j+1]+(xys[j+1]-xys[j])*movey[i][j]);
			}
		}
	}

	// rep(i,_n){
	// 	print(xys[i]);
	// }

	// print(dp[1][4]);

	rep(_,q){
		int t,_x;
		cin>>t>>_x;
		pii p={t-_x,t+_x};
		int x=p.fi,y=p.se;
		// print(x,y);
		p.fi=ced(p.fi);
		p.se=ced(p.se);
		p.fi=min(_n,p.fi);
		p.se=min(_n,p.se);
		int ans=0;
		ans=dp[p.fi][p.se];
		if(p.se){
			rng(i,p.fi,_n){
				ans=max(ans,dp[i][p.se]+movey[i][p.se-1]*(xys[p.se]-y));
			}
		}
		if(p.fi){
			// print(x,xys[p.fi]);
			rng(j,p.se,_n){
				// print(xys[j],movex[p.fi-1][j]);
				ans=max(ans,dp[p.fi][j]+movex[p.fi-1][j]*(xys[p.fi]-x));
			}
		}
		print(ans/2);
	}
//
	return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25049 ms 639820 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 1658672 KB Output is correct
2 Correct 1208 ms 1658788 KB Output is correct
3 Correct 1177 ms 1657376 KB Output is correct
4 Correct 134 ms 184780 KB Output is correct
5 Correct 843 ms 1152264 KB Output is correct
6 Correct 998 ms 1394024 KB Output is correct
7 Correct 1274 ms 1656168 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 1658672 KB Output is correct
2 Correct 1208 ms 1658788 KB Output is correct
3 Correct 1177 ms 1657376 KB Output is correct
4 Correct 134 ms 184780 KB Output is correct
5 Correct 843 ms 1152264 KB Output is correct
6 Correct 998 ms 1394024 KB Output is correct
7 Correct 1274 ms 1656168 KB Output is correct
8 Correct 1805 ms 1658796 KB Output is correct
9 Correct 1906 ms 1658968 KB Output is correct
10 Incorrect 1645 ms 1657512 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 1658672 KB Output is correct
2 Correct 1208 ms 1658788 KB Output is correct
3 Correct 1177 ms 1657376 KB Output is correct
4 Correct 134 ms 184780 KB Output is correct
5 Correct 843 ms 1152264 KB Output is correct
6 Correct 998 ms 1394024 KB Output is correct
7 Correct 1274 ms 1656168 KB Output is correct
8 Correct 1805 ms 1658796 KB Output is correct
9 Correct 1906 ms 1658968 KB Output is correct
10 Incorrect 1645 ms 1657512 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25049 ms 639820 KB Time limit exceeded
2 Halted 0 ms 0 KB -