CodeTON Round 5 : E. Tenzing and Triangle

設定はややこしいけど問題はそこまで難しくない。
https://codeforces.com/contest/1842/problem/E

問題

2次元座標上で、(0,0)-(0,K)-(K,0)で囲まれた領域内にN個の点の位置が指定される。
これらを、以下の手段を用いてすべて消したい。
最小総コストを求めよ。

• x=aとy=bとx+y=kで囲まれた三角形内の点を消す。この三角形の短辺の長さをLとすると、L×Aのコストがかかる。
• i番の点を消す。この時C[i]のコストがかかる。

解法

X座標を走査しながら、特定のY座標以上の点を消していくことを考える。
この時、区間加算・区間最小値を取れるSegTreeを用いて、各Y座標より上の点を消し去る場合の最小コストを求めて行こう。

int N,K,A;

static ll const def=1LL<<60;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l || y<=x) return def;
		if(x<=l && r<=y) return ma[k];
		return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r||y<=x) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+min(ma[k*2],ma[k*2+1]);
		}
	}
};
SegTree_3<ll,1<<20> st;
vector<pair<int,int>> ev[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>A;
	vector<vector<int>> cand;
	ll sum=0;
	FOR(i,N) {
		int x,y,c;
		cin>>x>>y>>c;
		sum+=c;
		ev[y].push_back({x,c});
	}
	st.update(0,K,1LL<<60);
	st.update(K,K+1,sum+1LL*K*A);
	
	for(x=1;x<=K;x++) {
		y=K-x;
		ll v=1LL<<60;
		//消さない
		if(x) {
			v=min(v,st.getval(y+1,y+2)-(y+1)*A);
		}
		FORR2(x2,c,ev[y]) {
			st.update(y+x-x2,K+1,-c);
		}
		//消す
		v=min(v,st.getval(y+1,K+1)-y*A);
		st.update(y,y+1,v+(y*A)-(1LL<<60));
		
	}
	
	cout<<st.getval(0,1)<<endl;
	
}

まとめ

SegTreeの持ち方とかちょっと迷うけど、考察自体は易しめ。