Cod sursa(job #3132556)

Utilizator rahulvermaRahul Verma rahulverma Data 23 mai 2023 02:50:41
Problema Branza Scor 0
Compilator java Status done
Runda Arhiva de probleme Marime 1.06 kb
import java.io.*;
import java.util.*;
public class cheese {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("branza.in"));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(st.nextToken());
		int t = Integer.parseInt(st.nextToken());
		Deque<Integer> d = new LinkedList();
		int[] c = new int[n];
		int[] p = new int[n];
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			c[i] = Integer.parseInt(st.nextToken());
			p[i] = Integer.parseInt(st.nextToken());
		}
		long ans = 0;
		for(int i = 0; i < n; i++) {
			while(!d.isEmpty() && i - d.peekFirst() > t) {
				d.pollFirst();
			}
			while(!d.isEmpty() && c[d.peekLast()] + ((long) s) * (long)((long) (i - d.peekLast())) >= c[i]) {
				d.pollLast();
			}
			d.add(i);
			ans += (long) p[i] * (((long) c[d.peekFirst()]) + ((long) s)*((long) i - d.peekFirst()));
		}
		PrintWriter pw = new PrintWriter("branza.out");
		pw.println(ans);
		pw.close();
	}

}