結果
問題 | No.989 N×Mマス計算(K以上) |
ユーザー |
![]() |
提出日時 | 2020-02-14 22:13:04 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 460 ms / 2,000 ms |
コード長 | 2,988 bytes |
コンパイル時間 | 2,566 ms |
コンパイル使用メモリ | 90,432 KB |
実行使用メモリ | 61,028 KB |
最終ジャッジ日時 | 2024-10-06 12:22:46 |
合計ジャッジ時間 | 7,453 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
ソースコード
import java.io.OutputStream;import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.io.IOException;import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.InputStream;import java.util.*;public class Main {public static boolean isOK(int index, long key, long[] a, char op) {if (a[index] >= key) return true;else return false;}public static int binary_search(long key, long[] a, char op) {int left = -1;int right = a.length;while (right - left > 1) {int mid = left + (right - left) / 2;if (isOK(mid, key, a, op)) right = mid;else left = mid;}return right;}public static void main(String[] args) {InputStream inputStream = System.in;OutputStream outputStream = System.out;InputReader in = new InputReader(inputStream);PrintWriter out = new PrintWriter(outputStream);int N = in.nextInt();int M = in.nextInt();int K = in.nextInt();String S = in.next();Long[] B = new Long[M];Long[] A = new Long[N];// long B_sum = 0L;// long A_sum = 0L;for (int i=0;i<M;i++) {B[i] = in.nextLong();// B_sum += B[i];}for (int i=0;i<N;i++) {A[i] = in.nextLong();// A_sum += A[i];}Arrays.sort(B);long ans = 0L;char op = S.charAt(0);for (int i=0;i<N;i++) {long tmp = 0;if (op=='+') tmp = K-A[i];if (op=='*') tmp = (K+A[i]-1)/A[i];// ans += binary_search(tmp, B, op);int index = ~Arrays.binarySearch(B, tmp, (o1, o2)->o1>=o2?1:-1);ans += M-index;}out.println(ans);// B_sum%=K;// A_sum%=K;// if (S.charAt(0)=='+') {// out.println((N*B_sum%K+M*A_sum%K)%K);// } else { // S.charAt(0)=='*'// long ans = 0L;// out.println(B_sum*A_sum%K);// }out.close();}static class InputReader {public BufferedReader reader;public StringTokenizer tokenizer;public InputReader(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new StringTokenizer(reader.readLine());} catch (IOException e) {throw new RuntimeException(e);}}return tokenizer.nextToken();}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}}}