Day 1<\/p>\n
…<\/p>\n
…<\/p>\n
<\/p>\n
\r\nconst int N = 100009;\r\npair<LL, LL> a[N], b[N];\r\n\r\n#define x first\r\n#define y second\r\n\r\nLL f(int u, int v){\r\n return a[u].y-a[v].x <= 0 ? 0 : (a[v].y-a[u].x)*(a[u].y-a[v].x);\r\n}\r\n\r\nbool cmp(const pair<LL, LL>& a, const pair<LL, LL>& b){\r\n return a.x<b.x || a.x==b.x && a.y>b.y ;\r\n}\r\n\r\nint main(){\r\n int n; while (cin>>n){\r\n REP(i, n)\r\n scanf("%lld %lld", &b[i].x, &b[i].y);\r\n\r\n LL res=0; int m=0; sort(b, b+n, cmp); for (int i=0,j;i<n;i=j){\r\n j=i+1; while (j<n && b[j].y<b[i].y){\r\n checkMax(res, (b[j].y-b[j].x)*(b[i].y-b[i].x));\r\n j++;\r\n }\r\n a[m++]=b[i];\r\n }\r\n\r\n n = m; int j = 1; checkMax(res,f(0,1)); FOR(i, 2, n){\r\n checkMax(res, f(j++,i) );\r\n while (j<i && f(j,i) >res)\r\n res=f(j++, i);\r\n }\r\n cout<<res<<endl;\r\n }\r\n}\r\n<\/pre>\n\r\nconst int N = 109, M = 10;\r\n\r\nbool dp[N+1][M+1][M+1][1<<M]; LL bonus[1<<M];\r\nint a[M], b[M], c[M];\r\nint n, m, p;\r\n\r\nVI L, Lb;\r\nbool G[M][M*M];\r\n\r\n\r\nLL f(int s){\r\n LL ans = 0;\r\n REP(i, m) if (_1(s, i)){\r\n ans += b[i];\r\n }\r\n REP(i, SZ(L)) if ((s&L[i]) == L[i]){\r\n ans += Lb[i];\r\n }\r\n return ans;\r\n}\r\n\r\n\r\nint main() {\r\n\r\n\/*\r\n#ifndef ONLINE_JUDGE\r\n\tfreopen("in.txt", "r", stdin);\r\n#endif\r\n*\/\r\n\r\n Rush{\r\n\r\n RD(n, m, p); REP(i, m) RD(a[i]); REP(i, m) RD(c[i]); REP(i, m) RD(b[i]);\r\n\r\n int x, y; CLR(L, Lb); REP(i, p){\r\n RD(x, y); int s = 0;REP(j, x) s |= _1(RD()-1);\r\n \/\/ cout << s << endl;\r\n L.PB(s); Lb.PB(y);\r\n }\r\n\r\n RST(G); REP(i, m){\r\n if (a[i] == 0) continue;\r\n if (a[i] == 1){\r\n REP(j, m) if (RD() == 1) G[i][j] = true;\r\n }\r\n else {\r\n REP_2(j, k, m, m) if (RD() == 1) G[i][j*m+k] = true;\r\n }\r\n }\r\n\r\n REP_C(s, _1(m)) bonus[s] = f(s);\r\n FLC(dp, false); dp[0][m][m][0] = true;\r\n\r\n LL ans = 0;\r\n\r\n FOR_1(i, 0, n) REP(l1, m+1) REP(l2, m+1) REP_C(s, _1(m)){\r\n if (!dp[i][l1][l2][s]) continue;\r\n\r\n \/\/cout << i << " " << s << endl;\r\n\r\n if (i == n) checkMax(ans, bonus[s]);\r\n\r\n REP(k, m) if (i + c[k] <= n){\r\n if (!a[k] || a[k] == 1 && l2 != m && G[k][l2] || a[k] == 2 && l1 != m && l2 != m && G[k][l1*m+l2]){\r\n dp[i+c[k]][l2][k][s|_1(k)] = true;\r\n }\r\n }\r\n }\r\n\r\n\/*\r\n REP_C(i, _1(m)){\r\n cout << i << " " << f(i) << endl;\r\n }\r\n *\/\r\n\r\n cout << ans << endl;\r\n }\r\n}\r\n\r\n\r\n\/*\r\n1110\r\n\/\/ 101\r\n\r\n*\/\r\n<\/pre>\nDay 2<\/p>\n
Brief description: <\/h3>\n
…<\/p>\n
Analysis: <\/h3>\n
…<\/p>\n
\r\n\r\nconst int N = 1009;\r\n\r\n\r\nint x[N], y[N], a[N], b[N], W[N];\r\nDB vx[N], vy[N];\r\nint n;\r\n\r\n\r\nVD L;\r\n\r\nint main(){\r\n\r\n\/*\r\n#ifdef LOCAL\r\n freopen("in.txt", "r", stdin);\r\n#endif\r\n*\/\r\n\r\n while (scanf("%d", &n) != EOF && n){\r\n\r\n REP(i, n){\r\n RD(x[i], y[i], a[i], b[i]);\r\n vx[i] = DB (a[i] - x[i]) \/ 10;\r\n vy[i] = DB (b[i] - y[i]) \/ 10;\r\n }\r\n\r\n if (n <= 2){\r\n cout << n << endl;\r\n continue;\r\n }\r\n\r\n CLR(L);\r\n\r\n L.PB(0), L.PB(10);\r\n\r\n\r\n REP(i, n) FOR(j, i+1, n) FOR(k, j+1, n){\r\n\r\n \/\/ Po v1 = PO( (x[j] + vx[j] * t) - (x[i] + vx[i] * t), (y[j] + vy[j] * t) - (y[i] + vy[i] * t) );\r\n \/\/ Po v2 = PO( (x[k] + vx[k] * t) - (x[i] + vx[i] * t), (y[k] + vy[k] * t) - (y[i] + vy[i] * t) );\r\n\r\n\r\n \/\/(x[j] - x[i]) + t (vx[j] - vx[i]) (y[k] - y[i]) + t (vy[k] - vy[i])\r\n \/\/ =\r\n \/\/(x[k] - x[i]) + t (vx[k] - vx[i]) (y[j] - y[i]) + t (vy[j] - vy[i])\r\n\r\n\r\n DB c = (x[j] - x[i]) * (y[k] - y[i]) - (x[k] - x[i]) * (y[j] - y[i]);\r\n DB b = (vx[j] - vx[i]) * (y[k] - y[i]) + (vy[k] - vy[i]) * (x[j] - x[i])\r\n - ((vx[k] - vx[i]) * (y[j] - y[i]) + (vy[j] - vy[i]) * (x[k] - x[i]));\r\n DB a = (vx[j] - vx[i]) * (vy[k] - vy[i]) - (vx[k] - vx[i]) * (vy[j] - vy[i]);\r\n\r\n\r\n if (!sgn(a)){\r\n\r\n if (sgn(b)){\r\n DB t1 = (-c \/ b);\r\n if (sgn(t1) >= 0 || sgn(t1, 10) <= 0){\r\n L.PB(t1);\r\n }\r\n }\r\n continue;\r\n }\r\n\r\n\r\n DB delta = sqr(b) - 4 * a * c;\r\n\r\n \/\/ cout << i << " " << j << " " << k << " " << delta << endl;\r\n\r\n if (sgn(delta) < 0) continue;\r\n if (!sgn(delta)){\r\n\r\n DB t = -b \/ (2*a);\r\n\/\/ cout << t << endl;\r\n if (sgn(t) < 0 || sgn(t, 10) > 0) continue;\r\n\r\n Po v1 = Po( (x[j] + vx[j] * t) - (x[i] + vx[i] * t), (y[j] + vy[j] * t) - (y[i] + vy[i] * t) );\r\n Po v2 = Po( (x[k] + vx[k] * t) - (x[i] + vx[i] * t), (y[k] + vy[k] * t) - (y[i] + vy[i] * t) );\r\n\r\n\/*\r\n if (sgn(det(v1, v2))){\r\n cout << "Error" << endl;\r\n }\r\n *\/\r\n }\r\n else {\r\n\r\n\r\n DB t1 = (-b + sqrt(delta)) \/ (2*a);\r\n if (sgn(t1) >= 0 || sgn(t1, 10) <= 0){\r\n L.PB(t1);\r\n }\r\n\r\n t1 = (-b - sqrt(delta)) \/ (2*a);\r\n if (sgn(t1) >= 0 || sgn(t1, 10) <= 0){\r\n L.PB(t1);\r\n }\r\n }\r\n }\r\n\r\n SRT(L);\r\n L.resize(unique(ALL(L)) - L.begin());\r\n\r\n\r\n int ans = 2;\r\n\r\n\/\/ cout << n << endl;\r\n\r\n REP(ii, SZ(L)){\r\n\r\n DB t = L[ii];\r\n\r\n\r\n vector<Po> pp; CLR(pp);\r\n REP(i, n){\r\n pp.PB( Po( (x[i] + vx[i] * t), (y[i] + vy[i] * t) ));\r\n }\r\n\r\n SRT(pp);\r\n\r\n vector<Po> ppp = pp;\r\n\r\n\r\n RST(W);\r\n\r\n\r\n pp.resize( unique( ALL(pp) ) - pp.begin() );\r\n\r\n\r\n\r\n\r\n\r\n\r\n int nn = SZ(pp);\r\n REP(i, nn){\r\n\r\n REP(j, n) if ( pp[i] == ppp[j] ) ++ W[i];\r\n\r\n }\r\n\r\n\r\n\r\n REP(i, nn) FOR(j, i+1, nn){\r\n\r\n Po v1 = pp[j] - pp[i];\r\n\r\n int cnt = W[i] + W[j];\r\n\r\n FOR(k, j+1, nn){\r\n\r\n Po v2 = pp[k] - pp[i];\r\n\r\n if (!sgn(det(v1, v2))){\r\n cnt += W[k];\r\n }\r\n\r\n }\r\n\r\n checkMax(ans, cnt);\r\n }\r\n }\r\n\r\n cout << ans << endl;\r\n\r\n }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Day 1 Brief description: … Analysis: …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[74],"tags":[24],"class_list":["post-245","post","type-post","status-publish","format-standard","hentry","category-astar","tag-24"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-3X","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/245","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=245"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/245\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=245"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=245"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=245"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}