# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

922702 | 2024-02-06T03:25:19 Z | golions | Potatoes and fertilizers (LMIO19_bulves) | Java 11 | 740 ms | 54112 KB |

//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]; for(int k = 1; k <= n; k++){ StringTokenizer st = new StringTokenizer(f.readLine()); long a = Long.parseLong(st.nextToken()); long b = Long.parseLong(st.nextToken()); d[k] = a-b; pd[k] = d[k] + pd[k-1]; } long x0 = 0L; //value at 0 PriorityQueue<Long> pq = new PriorityQueue<Long>(10,Collections.reverseOrder()); for(int k = 1; k <= n; k++){ if(pd[k] <= 0){ x0 += -1L * pd[k]; //basically starting at 0, and updating x0 //slope changing point at 0 is implied, no need to store if(!pq.isEmpty()){ pq.poll(); } } else { x0 += pd[k]; pq.add(pd[k]); pq.add(pd[k]); pq.poll(); } } //get value at pd[n] long answer = x0; long slope = (long)pq.size(); //pd[n] is guaranteed to be in the pq, unless it is 0 if(pd[n] > 0){ //need to sort elements in pq in the other order PriorityQueue<Long> pq2 = new PriorityQueue<Long>(); while(!pq.isEmpty()) pq2.add(pq.poll()); long i = 0L; while(true){ long top = pq2.poll(); answer -= (top - i) * slope; i = top; slope--; if(top == pd[n]) break; } } out.println(answer); out.close(); } }

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 55 ms | 10564 KB | Output is correct |

2 | Correct | 97 ms | 11660 KB | Output is correct |

3 | Correct | 130 ms | 12888 KB | Output is correct |

4 | Correct | 228 ms | 15636 KB | Output is correct |

5 | Correct | 242 ms | 16708 KB | Output is correct |

6 | Correct | 346 ms | 31876 KB | Output is correct |

7 | Correct | 344 ms | 31332 KB | Output is correct |

8 | Correct | 425 ms | 44956 KB | Output is correct |

9 | Correct | 348 ms | 30520 KB | Output is correct |

10 | Correct | 354 ms | 31540 KB | Output is correct |

11 | Correct | 347 ms | 32136 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 55 ms | 10564 KB | Output is correct |

2 | Correct | 97 ms | 11660 KB | Output is correct |

3 | Correct | 130 ms | 12888 KB | Output is correct |

4 | Correct | 228 ms | 15636 KB | Output is correct |

5 | Correct | 242 ms | 16708 KB | Output is correct |

6 | Correct | 346 ms | 31876 KB | Output is correct |

7 | Correct | 344 ms | 31332 KB | Output is correct |

8 | Correct | 425 ms | 44956 KB | Output is correct |

9 | Correct | 348 ms | 30520 KB | Output is correct |

10 | Correct | 354 ms | 31540 KB | Output is correct |

11 | Correct | 347 ms | 32136 KB | Output is correct |

12 | Correct | 316 ms | 20956 KB | Output is correct |

13 | Correct | 457 ms | 32880 KB | Output is correct |

14 | Correct | 350 ms | 31084 KB | Output is correct |

15 | Correct | 627 ms | 52252 KB | Output is correct |

16 | Correct | 644 ms | 43136 KB | Output is correct |

17 | Correct | 318 ms | 26904 KB | Output is correct |

18 | Correct | 104 ms | 13188 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 55 ms | 10564 KB | Output is correct |

2 | Correct | 97 ms | 11660 KB | Output is correct |

3 | Correct | 104 ms | 13188 KB | Output is correct |

4 | Correct | 48 ms | 9300 KB | Output is correct |

5 | Correct | 87 ms | 9916 KB | Output is correct |

6 | Correct | 96 ms | 9640 KB | Output is correct |

7 | Correct | 129 ms | 10896 KB | Output is correct |

8 | Correct | 119 ms | 10776 KB | Output is correct |

9 | Correct | 141 ms | 11368 KB | Output is correct |

10 | Correct | 115 ms | 10948 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 55 ms | 10564 KB | Output is correct |

2 | Correct | 97 ms | 11660 KB | Output is correct |

3 | Correct | 130 ms | 12888 KB | Output is correct |

4 | Correct | 48 ms | 9300 KB | Output is correct |

5 | Correct | 87 ms | 9916 KB | Output is correct |

6 | Correct | 96 ms | 9640 KB | Output is correct |

7 | Correct | 129 ms | 10896 KB | Output is correct |

8 | Correct | 119 ms | 10776 KB | Output is correct |

9 | Correct | 141 ms | 11368 KB | Output is correct |

10 | Correct | 115 ms | 10948 KB | Output is correct |

11 | Correct | 104 ms | 13188 KB | Output is correct |

12 | Correct | 144 ms | 12264 KB | Output is correct |

13 | Correct | 155 ms | 12680 KB | Output is correct |

14 | Correct | 169 ms | 12376 KB | Output is correct |

15 | Correct | 156 ms | 14236 KB | Output is correct |

16 | Correct | 169 ms | 13384 KB | Output is correct |

17 | Correct | 162 ms | 13396 KB | Output is correct |

18 | Correct | 145 ms | 13464 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 55 ms | 10564 KB | Output is correct |

2 | Correct | 97 ms | 11660 KB | Output is correct |

3 | Correct | 130 ms | 12888 KB | Output is correct |

4 | Correct | 48 ms | 9300 KB | Output is correct |

5 | Correct | 87 ms | 9916 KB | Output is correct |

6 | Correct | 96 ms | 9640 KB | Output is correct |

7 | Correct | 129 ms | 10896 KB | Output is correct |

8 | Correct | 119 ms | 10776 KB | Output is correct |

9 | Correct | 141 ms | 11368 KB | Output is correct |

10 | Correct | 115 ms | 10948 KB | Output is correct |

11 | Correct | 228 ms | 15636 KB | Output is correct |

12 | Correct | 242 ms | 16708 KB | Output is correct |

13 | Correct | 346 ms | 31876 KB | Output is correct |

14 | Correct | 344 ms | 31332 KB | Output is correct |

15 | Correct | 425 ms | 44956 KB | Output is correct |

16 | Correct | 348 ms | 30520 KB | Output is correct |

17 | Correct | 354 ms | 31540 KB | Output is correct |

18 | Correct | 347 ms | 32136 KB | Output is correct |

19 | Correct | 316 ms | 20956 KB | Output is correct |

20 | Correct | 457 ms | 32880 KB | Output is correct |

21 | Correct | 350 ms | 31084 KB | Output is correct |

22 | Correct | 627 ms | 52252 KB | Output is correct |

23 | Correct | 644 ms | 43136 KB | Output is correct |

24 | Correct | 318 ms | 26904 KB | Output is correct |

25 | Correct | 144 ms | 12264 KB | Output is correct |

26 | Correct | 155 ms | 12680 KB | Output is correct |

27 | Correct | 169 ms | 12376 KB | Output is correct |

28 | Correct | 156 ms | 14236 KB | Output is correct |

29 | Correct | 169 ms | 13384 KB | Output is correct |

30 | Correct | 162 ms | 13396 KB | Output is correct |

31 | Correct | 145 ms | 13464 KB | Output is correct |

32 | Correct | 104 ms | 13188 KB | Output is correct |

33 | Correct | 352 ms | 21520 KB | Output is correct |

34 | Correct | 509 ms | 33132 KB | Output is correct |

35 | Correct | 712 ms | 49168 KB | Output is correct |

36 | Correct | 740 ms | 47052 KB | Output is correct |

37 | Correct | 638 ms | 51300 KB | Output is correct |

38 | Correct | 650 ms | 54112 KB | Output is correct |

39 | Correct | 581 ms | 48240 KB | Output is correct |

40 | Correct | 617 ms | 43072 KB | Output is correct |

41 | Correct | 484 ms | 36688 KB | Output is correct |

42 | Correct | 451 ms | 35532 KB | Output is correct |

43 | Correct | 460 ms | 32192 KB | Output is correct |

44 | Correct | 437 ms | 30108 KB | Output is correct |

45 | Correct | 613 ms | 40152 KB | Output is correct |

46 | Correct | 601 ms | 45636 KB | Output is correct |

47 | Correct | 541 ms | 37892 KB | Output is correct |