Codeforces Round #132 (Div. 2) D : Hot Days

問題概要

長さN(<10^5)の配列x, t, T, cがある。Mをいくつかに分ける。分けたグループの個数*cと、それぞれのグループについて、t[i]+size がTを越えたらグループのそれぞれの要素につきxのコストがかかる。全体での最小コストを求める問題。

解法

独立な問題をN個解く。各点での最適解は全部まとめるかペナルティを得ない範囲で可能な限り詰め込むかの2択なので小さい方を選べばよい。

acceptされたコード

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;


typedef long long int64;

const int MAX_N = (int)(1e5);
const int MAX_M = (int)(1e6);
const int64 INF = (1LL<<62) - 2;

int N, M;
int ts[MAX_N], Ts[MAX_N], cost[MAX_N], xs[MAX_N];

void init() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; ++i) {
		scanf("%d%d%d%d", ts+i, Ts+i, xs+i, cost+i);
	}
}

int64 solve() {
	int64 ans = 0;

	for (int i = 0; i < N; ++i) {
		if (ts[i] >= Ts[i]) {
			ans += cost[i] + (int64)xs[i] * M;
		}
		else {
			int64 t1 = cost[i] + (int64)xs[i] * M;
			int t = Ts[i] - ts[i];
			int64 t2 = (int64)cost[i] * ((M + t - 1) / t);
			if (t > M) {
				t2 = cost[i];
			}
			ans += min(t1, t2);
		}
	}

	return ans;
}

int main() {
	init();
	cout << solve() << endl;
	return 0;
}