Submission #922702

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
922702	2024-02-06 03:25:19	golions	Potatoes and fertilizers (LMIO19_bulves)	Java	100 / 100	740 ms	54112 KiB

bulves

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//make sure to make new file!
import java.io.*;
import java.util.*;
//https://usaco.guide/adv/slope-trick?lang=cpp
/*
ex: a-b array is 2 2 2 -5 2 2 2
prefix sums: 2 4 6 1 3 5 7
optimal ending configuration: 2 1 0 0 0 2 2
prefix sums: 2 3 3 3 3 5 7
note that this is nondecreasing because optimal ending configuration has to be nonnegative
cost of this configuration is sum of abs of difference with original prefix sums
the difference is basically the number of fertilizer that has to go over that gap
find the prefix sum of optimal ending configuration
so the solution is to use slope trick to optimize dp[x][d] dp, (first x numbers, min cost to get last value of prefix sum <= d)
transition to d2 is add |pd[x] - d2| -> add pd[x] twice, then get suffix min by removing biggest point
*/
public class bulves{
   
   public static void main(String[] args)throws IOException{
      BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(System.out);
      
      int n = Integer.parseInt(f.readLine());
      
      long[] d = new long[n+1];
      long[] pd = new long[n+1];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36