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
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
import java.util.Scanner;

/**
 * @author Jaca777
 *         Created 2015-09-28 at 17
 */
public class sia {
    private static class Mowing {
        private long limit;
        private long day;

        public Mowing(long day, long limit) {
            this.limit = limit;
            this.day = day;
        }

    }

    private static class Input {

        private int area;
        private int types;
        private int[] growthRate;
        private Mowing[] mowings;

        public Input(int area, int types, int[] growthRate, Mowing[] mowings) {
            this.area = area;
            this.types = types;
            this.growthRate = growthRate;
            this.mowings = mowings;
        }

    }

    private static class Output {
        private long[] weights;

        private Output(long[] weights) {
            this.weights = weights;
        }

        public long[] getWeights() {
            return weights;
        }

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            for (long weight : weights) {
                builder.append(weight);
                builder.append('\n');
            }
            return builder.toString();
        }
    }

    public static Output solve(Input input) {
        Mowing initialMowing = new Mowing(0, 0);

        Mowing[] mowings = input.mowings;
        long[] lastState = new long[input.area];
        long[] weights = new long[input.mowings.length];
        for (int i = 0; i < mowings.length; i++) {
            Mowing lastMowing = (i > 0) ? mowings[i - 1] : initialMowing;
            Mowing mowing = mowings[i];
            long delta = mowing.day - lastMowing.day;
            for (int j = 0; j < input.area; j++) {
                long currentState = lastState[j] + input.growthRate[j] * delta;
                long weight = Math.max(currentState - mowing.limit, 0);
                weights[i] += weight;
                lastState[j] = currentState - weight;
            }
        }
        return new Output(weights);
    }

    public static Input readSystemInput() {
        Scanner scanner = new Scanner(System.in);
        int area = scanner.nextInt();
        int types = area;

        int cutsAmount = scanner.nextInt();

        int[] growthRate = new int[types];
        for (int i = 0; i < growthRate.length; i++) {
            growthRate[i] = scanner.nextInt();
        }

        Mowing[] mowings = new Mowing[cutsAmount];
        for (int i = 0; i < mowings.length; i++) {
            mowings[i] = new Mowing(scanner.nextInt(), scanner.nextInt());
        }

        scanner.close();
        return new Input(area, types, growthRate, mowings);
    }

    public static void main(String... args) {
        Input input = readSystemInput();
        System.out.println(solve(input));
    }

}