fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll=long long;
  5. #define int ll
  6.  
  7. #define rng(i,a,b) for(int i=int(a);i<int(b);i++)
  8. #define rep(i,b) rng(i,0,b)
  9. #define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
  10. #define per(i,b) gnr(i,0,b)
  11. #define pb push_back
  12. #define eb emplace_back
  13. #define a first
  14. #define b second
  15. #define bg begin()
  16. #define ed end()
  17. #define all(x) x.bg,x.ed
  18. #define si(x) int(x.size())
  19. #ifdef LOCAL
  20. #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
  21. #else
  22. #define dmp(x) void(0)
  23. #endif
  24.  
  25. template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
  26. template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}
  27.  
  28. template<class t> using vc=vector<t>;
  29. template<class t> using vvc=vc<vc<t>>;
  30.  
  31. using pi=pair<int,int>;
  32. using vi=vc<int>;
  33.  
  34. template<class t,class u>
  35. ostream& operator<<(ostream& os,const pair<t,u>& p){
  36. 	return os<<"{"<<p.a<<","<<p.b<<"}";
  37. }
  38.  
  39. template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
  40. 	os<<"{";
  41. 	for(auto e:v)os<<e<<",";
  42. 	return os<<"}";
  43. }
  44.  
  45. #define mp make_pair
  46. #define mt make_tuple
  47. #define one(x) memset(x,-1,sizeof(x))
  48. #define zero(x) memset(x,0,sizeof(x))
  49. #ifdef LOCAL
  50. void dmpr(ostream&os){os<<endl;}
  51. template<class T,class... Args>
  52. void dmpr(ostream&os,const T&t,const Args&... args){
  53. 	os<<t<<" ";
  54. 	dmpr(os,args...);
  55. }
  56. #define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
  57. #else
  58. #define dmp2(...) void(0)
  59. #endif
  60.  
  61. using uint=unsigned;
  62. using ull=unsigned long long;
  63.  
  64. template<class t,size_t n>
  65. ostream& operator<<(ostream&os,const array<t,n>&a){
  66. 	return os<<vc<t>(all(a));
  67. }
  68.  
  69. template<int i,class T>
  70. void print_tuple(ostream&,const T&){
  71. }
  72.  
  73. template<int i,class T,class H,class ...Args>
  74. void print_tuple(ostream&os,const T&t){
  75. 	if(i)os<<",";
  76. 	os<<get<i>(t);
  77. 	print_tuple<i+1,T,Args...>(os,t);
  78. }
  79.  
  80. template<class ...Args>
  81. ostream& operator<<(ostream&os,const tuple<Args...>&t){
  82. 	os<<"{";
  83. 	print_tuple<0,tuple<Args...>,Args...>(os,t);
  84. 	return os<<"}";
  85. }
  86.  
  87. template<class t>
  88. void print(t x,int suc=1){
  89. 	cout<<x;
  90. 	if(suc==1)
  91. 		cout<<"\n";
  92. 	if(suc==2)
  93. 		cout<<" ";
  94. }
  95.  
  96. ll read(){
  97. 	ll i;
  98. 	cin>>i;
  99. 	return i;
  100. }
  101.  
  102. vi readvi(int n,int off=0){
  103. 	vi v(n);
  104. 	rep(i,n)v[i]=read()+off;
  105. 	return v;
  106. }
  107.  
  108. pi readpi(int off=0){
  109. 	int a,b;cin>>a>>b;
  110. 	return pi(a+off,b+off);
  111. }
  112.  
  113. template<class T>
  114. void print(const vector<T>&v,int suc=1){
  115. 	rep(i,v.size())
  116. 		print(v[i],i==int(v.size())-1?suc:2);
  117. }
  118.  
  119. string readString(){
  120. 	string s;
  121. 	cin>>s;
  122. 	return s;
  123. }
  124.  
  125. template<class T>
  126. T sq(const T& t){
  127. 	return t*t;
  128. }
  129.  
  130. //#define CAPITAL
  131. void yes(bool ex=true){
  132. 	#ifdef CAPITAL
  133. 	cout<<"YES"<<"\n";
  134. 	#else
  135. 	cout<<"Yes"<<"\n";
  136. 	#endif
  137. 	if(ex)exit(0);
  138. 	#ifdef LOCAL
  139. 	cout.flush();
  140. 	#endif
  141. }
  142. void no(bool ex=true){
  143. 	#ifdef CAPITAL
  144. 	cout<<"NO"<<"\n";
  145. 	#else
  146. 	cout<<"No"<<"\n";
  147. 	#endif
  148. 	if(ex)exit(0);
  149. 	#ifdef LOCAL
  150. 	cout.flush();
  151. 	#endif
  152. }
  153. void possible(bool ex=true){
  154. 	#ifdef CAPITAL
  155. 	cout<<"POSSIBLE"<<"\n";
  156. 	#else
  157. 	cout<<"Possible"<<"\n";
  158. 	#endif
  159. 	if(ex)exit(0);
  160. 	#ifdef LOCAL
  161. 	cout.flush();
  162. 	#endif
  163. }
  164. void impossible(bool ex=true){
  165. 	#ifdef CAPITAL
  166. 	cout<<"IMPOSSIBLE"<<"\n";
  167. 	#else
  168. 	cout<<"Impossible"<<"\n";
  169. 	#endif
  170. 	if(ex)exit(0);
  171. 	#ifdef LOCAL
  172. 	cout.flush();
  173. 	#endif
  174. }
  175.  
  176. constexpr ll ten(int n){
  177. 	return n==0?1:ten(n-1)*10;
  178. }
  179.  
  180. const ll infLL=LLONG_MAX/3;
  181.  
  182. #ifdef int
  183. const int inf=infLL;
  184. #else
  185. const int inf=INT_MAX/2-100;
  186. #endif
  187.  
  188. int topbit(signed t){
  189. 	return t==0?-1:31-__builtin_clz(t);
  190. }
  191. int topbit(ll t){
  192. 	return t==0?-1:63-__builtin_clzll(t);
  193. }
  194. int botbit(signed a){
  195. 	return a==0?32:__builtin_ctz(a);
  196. }
  197. int botbit(ll a){
  198. 	return a==0?64:__builtin_ctzll(a);
  199. }
  200. int popcount(signed t){
  201. 	return __builtin_popcount(t);
  202. }
  203. int popcount(ll t){
  204. 	return __builtin_popcountll(t);
  205. }
  206. bool ispow2(int i){
  207. 	return i&&(i&-i)==i;
  208. }
  209. ll mask(int i){
  210. 	return (ll(1)<<i)-1;
  211. }
  212.  
  213. bool inc(int a,int b,int c){
  214. 	return a<=b&&b<=c;
  215. }
  216.  
  217. template<class t> void mkuni(vc<t>&v){
  218. 	sort(all(v));
  219. 	v.erase(unique(all(v)),v.ed);
  220. }
  221.  
  222. ll rand_int(ll l, ll r) { //[l, r]
  223. 	#ifdef LOCAL
  224. 	static mt19937_64 gen;
  225. 	#else
  226. 	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  227. 	#endif
  228. 	return uniform_int_distribution<ll>(l, r)(gen);
  229. }
  230.  
  231. template<class t>
  232. void myshuffle(vc<t>&a){
  233. 	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
  234. }
  235.  
  236. template<class t>
  237. int lwb(const vc<t>&v,const t&a){
  238. 	return lower_bound(all(v),a)-v.bg;
  239. }
  240.  
  241. vvc<int> readGraph(int n,int m){
  242. 	vvc<int> g(n);
  243. 	rep(i,m){
  244. 		int a,b;
  245. 		cin>>a>>b;
  246. 		//sc.read(a,b);
  247. 		a--;b--;
  248. 		g[a].pb(b);
  249. 		g[b].pb(a);
  250. 	}
  251. 	return g;
  252. }
  253.  
  254. vvc<int> readTree(int n){
  255. 	return readGraph(n,n-1);
  256. }
  257.  
  258. struct W{
  259. 	int val;
  260. 	int a,b,c,d;
  261. };
  262.  
  263. const int nmax=810;
  264. int bonus[nmax*2][nmax*2];
  265.  
  266. int sub(int S,vc<W> waf,vc<W> unko){
  267. 	vi xs{0,4*S},ys{0,4*S};
  268. 	for(auto&w:waf){
  269. 		w.c--;
  270. 		w.d++;
  271. 	}
  272. 	for(auto&w:unko){
  273. 		bool f=false;
  274. 		for(const auto&z:waf){
  275. 			if(w.a<=z.c&&z.d<=w.b){
  276. 				f=true;
  277. 				break;
  278. 			}
  279. 		}
  280. 		if(!f){
  281. 			swap(w.a,w.c);
  282. 			swap(w.b,w.d);
  283. 		}
  284. 		w.c=0;
  285. 		w.d=4*S;
  286. 	}
  287. 	waf.insert(waf.ed,all(unko));
  288. 	int n=si(waf);
  289. 	rep(i,n){
  290. 		xs.pb(waf[i].a);
  291. 		xs.pb(waf[i].c);
  292. 		ys.pb(waf[i].b);
  293. 		ys.pb(waf[i].d);
  294. 	}
  295. 	mkuni(xs);
  296. 	mkuni(ys);
  297. 	int len=si(ys);
  298. 	//vvc<int> bonus(si(xs)-1,vi(len));
  299. 	int wid=si(xs)-1;
  300. 	rep(i,wid)rep(j,len)bonus[i][j]=0;
  301. 	auto add=[&](int a,int b,int c){
  302. 		a=lwb(xs,a);
  303. 		b=lwb(ys,b);
  304. 		assert(a<wid);
  305. 		assert(0<b);
  306. 		bonus[a][b-1]+=c;
  307. 	};
  308. 	for(auto w:waf){
  309. 		add(w.a,w.b,-w.val);
  310. 		add(w.c,w.d,w.val);
  311. 	}
  312. 	rep(i,wid)per(j,len-1)bonus[i][j]+=bonus[i][j+1];
  313. 	vi dp(len);
  314. 	rep(i,wid){
  315. 		rep(j,len)dp[j]+=bonus[i][j];
  316. 		rng(j,1,len)chmax(dp[j],dp[j-1]);
  317. 	}
  318. 	//print(dp.back());
  319. 	return dp.back();
  320. }
  321.  
  322. void slv(){
  323. 	int S,n;cin>>S>>n;
  324. 	vc<W> waf;
  325. 	auto readpos=[&](){
  326. 		int x,y;cin>>x>>y;
  327. 		if(y==0)return x;
  328. 		else if(x==S)return S+y;
  329. 		else if(y==S)return S+S+S-x;
  330. 		else if(x==0)return S+S+S+S-y;
  331. 		else assert(0);
  332. 	};
  333. 	rep(i,n){
  334. 		int val;cin>>val;
  335. 		int a=readpos();
  336. 		int b=readpos();
  337. 		if(a>b)swap(a,b);
  338. 		int c=readpos();
  339. 		int d=readpos();
  340. 		if(c>d)swap(c,d);
  341. 		if(a<c){
  342. 			swap(a,c);
  343. 			swap(b,d);
  344. 		}
  345. 		//dmp2(i,a,b,c,d);
  346. 		waf.pb({val,a,b,c,d});
  347. 	}
  348. 	int ans=0;
  349. 	struct Q{
  350. 		int x,t,i;
  351. 		bool operator<(const Q&rhs)const{
  352. 			if(x!=rhs.x)return x<rhs.x;
  353. 			else if(t!=rhs.t)return t<rhs.t;
  354. 			else return i<rhs.i;
  355. 		}
  356. 	};
  357. 	vc<Q> qs;
  358. 	vc<W> unko;
  359. 	rep(i,n){
  360. 		if(waf[i].b<waf[i].d){
  361. 			qs.pb({waf[i].c,0,i});
  362. 			qs.pb({waf[i].d,1,i});
  363. 		}else{
  364. 			unko.pb(waf[i]);
  365. 			ans+=waf[i].val;
  366. 		}
  367. 	}
  368. 	sort(all(qs));
  369. 	vc<bool> cur(n);
  370. 	bool need=false;
  371. 	for(auto w:qs){
  372. 		if(w.t==0){
  373. 			cur[w.i]=true;
  374. 			need=true;
  375. 		}else{
  376. 			if(need){
  377. 				vc<W> tmp;
  378. 				rep(i,n)if(cur[i])tmp.pb(waf[i]);
  379. 				chmax(ans,sub(S,tmp,unko));
  380. 			}
  381. 			cur[w.i]=false;
  382. 			need=false;
  383. 		}
  384. 	}
  385. 	print(ans);
  386. }
  387.  
  388. signed main(){
  389. 	cin.tie(0);
  390. 	ios::sync_with_stdio(0);
  391. 	cout<<fixed<<setprecision(20);
  392.  
  393. 	int t;cin>>t;
  394. 	rep(i,t){
  395. 		cerr<<"Process Test "<<i+1<<endl;
  396. 		cout<<"Case #"<<i+1<<": ";
  397. 		slv();
  398. 	}
  399. }
  400.  
Success #stdin #stdout #stderr 0s 4484KB
comments (?)
stdin
copy 
7
10 3
20 0 4 10 4 0 6 10 6
30 0 8 10 8 0 9 10 9
40 2 0 2 10 5 0 5 10
4 3
10 0 1 1 0 0 2 2 0
20 0 2 2 4 0 3 1 4
30 2 0 2 4 3 0 3 4
4 4
10 0 1 1 0 0 2 2 0
20 4 2 2 4 4 3 3 4
30 0 2 2 4 0 3 1 4
40 4 1 3 0 4 2 2 0
5 4
1 0 1 5 1 0 2 5 2
2 0 2 5 2 0 3 5 3
4 0 3 5 3 0 4 5 4
8 0 4 5 4 0 1 5 1
10 5
3 4 0 0 3 6 0 8 10
4 7 10 10 7 10 5 5 10
6 4 10 2 0 0 9 2 10
3 10 5 6 0 9 0 10 4
1 0 4 10 5 10 7 0 6
10000 15
964 0 9688 10000 9757 0 5290 6888 0
1121 0 1389 1707 0 10000 4897 6073 10000
480 52 0 7636 10000 0 7970 5894 10000
232 3924 0 4373 10000 2183 10000 1472 0
133 2471 10000 0 4074 5240 10000 10000 5064
706 9853 10000 10000 6154 0 1824 395 10000
180 0 545 10000 2644 10000 3667 1372 10000
253 2305 0 0 1825 10000 7597 7210 0
758 9154 0 0 1748 0 9591 10000 9017
603 10000 3697 0 7106 3861 10000 0 8408
793 9724 0 10000 6555 0 3725 4425 10000
877 8090 10000 6852 0 10000 5453 8854 0
583 10000 2565 7605 0 0 6412 6778 0
1103 5303 10000 0 7918 0 3908 1146 0
86 8641 0 9846 10000 0 5456 5530 0
4000 30
119 4000 959 1713 0 99 0 0 773
58 414 4000 2804 0 4000 3461 2754 4000
282 2913 4000 0 2780 4000 1625 3427 0
244 4000 3384 46 4000 793 0 0 1333
232 1245 4000 0 2659 939 0 1380 4000
423 3556 0 2059 4000 2496 4000 4000 2941
55 2453 4000 4000 1446 1354 4000 1001 0
345 2992 0 0 237 3787 4000 3778 0
208 0 1081 147 0 241 4000 0 2018
88 4000 3288 0 1558 4000 3290 0 3177
309 1190 4000 0 3160 4000 2664 2173 0
400 1470 0 1295 4000 3021 0 4000 3716
408 0 3725 3407 4000 3474 4000 0 2548
154 59 4000 1923 0 2269 4000 4000 1075
221 357 0 3896 4000 0 1000 2862 4000
20 4000 1427 3506 0 2650 4000 4000 1776
333 2773 4000 4000 1978 3608 0 1714 4000
144 0 3360 85 0 4000 2253 1248 4000
522 2002 0 0 3704 0 3787 1289 4000
387 1556 4000 4000 2710 826 0 4000 44
405 0 3826 3448 0 4000 1888 519 4000
89 3409 4000 4000 1216 0 780 3245 4000
448 1533 4000 3501 0 3469 0 0 854
118 592 4000 0 1908 4000 773 2660 4000
372 0 1669 3074 0 2879 4000 4000 3636
283 4000 3549 2078 4000 4000 2056 631 0
446 0 3575 411 4000 962 4000 4000 133
484 0 147 2755 0 1001 4000 0 2018
139 0 251 3229 0 4000 3642 0 2816
151 4000 1647 3562 4000 3122 4000 2113 0
stdout
copy 
Case #1: 70
Case #2: 60
Case #3: 60
Case #4: 14
Case #5: 11
Case #6: 8160
Case #7: 7207
stderr
copy 
Process Test 1
Process Test 2
Process Test 3
Process Test 4
Process Test 5
Process Test 6
Process Test 7
https://ideone.com/cvJPLn
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!