Submission #95791

#	Time	Username	Problem	Language	Result	Execution time	Memory
95791		Martomate	Palembang Bridges (APIO15_bridge)	Java	0 / 100	113 ms	10824 KiB

bridge

import java.io.*;
import java.util.*;

public class bridge {
    public static void main(String[] args) {
        Kattio io = new Kattio(System.in);

        int K = io.getInt();
        int N = io.getInt();

        long same = 0;

        ArrayList<Person> persons = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            char P = io.getWord().charAt(0);
            int S = io.getInt();
            char Q = io.getWord().charAt(0);
            int T = io.getInt();

            if (P == Q)
                same += Math.abs(S - T);
            else
                persons.add(new Person(S, T));
        }

        if (K == 1) {
            int min = 0;
            int max = 1_000_000_000;

            while (min < max - 2) {
                int lo = min + (max - min) / 3;
                int hi = min + (max - min) * 2 / 3;

                long loVal = value(persons, lo);
                long hiVal = value(persons, hi);

                if (loVal < hiVal) {
                    max = hi;
                } else {
                    min = lo;
                }
            }

            int bestIdx = min;
            long best = Integer.MAX_VALUE;

            for (int i = min; i <= max; i++) {
                long now = value(persons, i);
                if (now < best) {
                    best = now;
                    bestIdx = i;
                }
            }

            io.println(same + best);
        } else if (K == 2) {

        }

        io.close();
    }

    private static long value(ArrayList<Person> persons, int bridge) {
        long sum = 0;

        for (Person p : persons) {
            sum += Math.abs(p.S - bridge);
            sum += Math.abs(p.T - bridge);
            sum++;
        }

        return sum;
    }

    static class Person {
        int S, T;

        Person(int s, int t) {
            S = s;
            T = t;
        }
    }
}

class Kattio extends PrintWriter {

    public Kattio(InputStream i) {
        super(new BufferedOutputStream(System.out));
        r = new BufferedReader(new InputStreamReader(i));
    }
    public Kattio(InputStream i, OutputStream o) {
        super(new BufferedOutputStream(o));
        r = new BufferedReader(new InputStreamReader(i));
    }

    public boolean hasMoreTokens() {
        return peekToken() != null;
    }

    public int getInt() {
        return Integer.parseInt(nextToken());
    }

    public double getDouble() {
        return Double.parseDouble(nextToken());
    }

    public long getLong() {
        return Long.parseLong(nextToken());
    }

    public String getWord() {
        return nextToken();
    }

    private BufferedReader r;
    private String line;
    private StringTokenizer st;
    private String token;

    private String peekToken() {
        if (token == null)
            try {
                while (st == null || !st.hasMoreTokens()) {
                    line = r.readLine();
                    if (line == null) return null;
                    st = new StringTokenizer(line);
                }
                token = st.nextToken();
            } catch (IOException e) { }
        return token;
    }

    private String nextToken() {
        String ans = peekToken();
        token = null;
        return ans;
    }

    public String getLine() {
        token = null;
        try {
            return r.readLine();
        } catch (IOException e) {}
        return null;
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37