oj.uz

Submission #922702

# Submission time Handle Problem Language Result Execution time Memory
922702 2024-02-06T03:25:19 Z golions Potatoes and fertilizers (LMIO19_bulves) Java 11
100 / 100
 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();
   }
   
      
}

Subtask #1
24.0 / 24.0

# 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

Subtask #2
10.0 / 10.0

# 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

Subtask #3
20.0 / 20.0

# 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

Subtask #4
10.0 / 10.0

# 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

Subtask #5
36.0 / 36.0

# 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