結果

問題 No.703 ゴミ拾い Easy
ユーザー vjudge1
提出日時 2025-03-21 17:22:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 160 ms / 1,500 ms
コード長 2,228 bytes
コンパイル時間 1,765 ms
コンパイル使用メモリ 166,360 KB
実行使用メモリ 107,036 KB
最終ジャッジ日時 2025-03-21 17:23:06
合計ジャッジ時間 8,227 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:68:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   68 |         scanf("%lld", &n);
      |         ~~~~~^~~~~~~~~~~~
main.cpp:70:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   70 |                 scanf("%lld", &a[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
main.cpp:72:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   72 |                 scanf("%lld", &x[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
main.cpp:74:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   74 |                 scanf("%lld", &y[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 10;
const long double eps = 1e-9;
const int INF = 2e18;
const int V = 1e5;
int x[N], y[N], a[N], sum, dp[N];
int n;
struct line{
	long double k, b;
	int ls, rs, l, r;
	bool flag = 0;
	int getY(int x){
		return x * k + b;
	}
	long double IntersectionX(line v){
		return (b - v.b) / (v.k - k);
	}
};
struct node{
	line tree[N * 4];
	int ncnt, root;
	void update(int &id, int tl, int tr, line p){
//		cout << tl << " " << tr << endl;
		if(id == 0){
			id = ++ncnt;
		}
		if(p.l <= tl  && tr <= p.r){
			if(tree[id].flag == 0){
				tree[id].k = p.k;
				tree[id].b = p.b;
				tree[id].flag = 1;
			}else if(p.getY(tl) < tree[id].getY(tl) && p.getY(tr) < tree[id].getY(tr)){
				tree[id].k = p.k;
				tree[id].b = p.b;
			}else if(p.getY(tl) < tree[id].getY(tl) || p.getY(tr) < tree[id].getY(tr)){
				int tm = (tl + tr) / 2;
				if(tree[id].getY(tm) > p.getY(tm)) swap(p.k, tree[id].k), swap(p.b, tree[id].b);
				if((long double) tm - p.IntersectionX(tree[id]) > eps){
					update(tree[id].ls, tl, tm, p);
				}else{
					update(tree[id].rs, tm + 1, tr, p);					
				}
			}
		}else{
			int tm = (tl + tr) / 2;
			if(p.l <= tm) update(tree[id].ls, tl, tm, p); 
			if(p.r > tm) update(tree[id].rs, tm + 1, tr, p);
		}
	}
	int query(int id, int tl, int tr, int x){
		if(id == 0) return INF;
		if(tl == tr){
			if(tree[id].flag) return tree[id].getY(x);
			return INF;
		}
		int tm = (tl + tr) / 2;
		int ret = (tree[id].flag == 1) ? tree[id].getY(x) : INF; 
		if(x <= tm){
			return min(ret, query(tree[id].ls, tl, tm, x));
		}else{
			return min(ret, query(tree[id].rs, tm + 1, tr, x));			
		}
	}
}LCtree;
signed main(){
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &x[i]);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &y[i]);	
	for(int i = 1; i <= n; i++){
		dp[i] = INF;
		line p; 
		p.k = -2 * x[i];
		p.b = y[i] * y[i] + dp[i - 1] + x[i] * x[i];
		p.l = 1;
		p.r = V;
		p.ls = p.rs = p.flag = 0;
		LCtree.update(LCtree.root, 1, V, p);
		dp[i] = LCtree.query(LCtree.root, 1, V, a[i]) + a[i] * a[i];
//		cout << i << " " << dp[i] << endl;
	}	
	printf("%lld\n", dp[n]);
}
0