oj.uz

Submission #367351

# Submission time Handle Problem Language Result Execution time Memory
367351 2021-02-16T23:11:17 Z JosephO_o Exhibition (JOI19_ho_t2) Java 11
50 / 100
 1000 ms 20056 KB 
//package power.rankings;

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

public class joi2019_ho_t2{//PowerRankings {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static class pair{
        int sz, val; public pair(int sz0, int val0){sz=sz0; val=val0;}
    }
    
    static class cmp implements Comparator<pair>{
        public int compare(pair a, pair b){
            if(a.val != b.val)return Integer.compare(a.val,b.val);
            else return Integer.compare(a.sz,b.sz);
        }
    }
    
    public static void main(String[] args) throws IOException {
        int n = readInt(), m = readInt(), framsz[] = new int[m+1]; 
        pair pic[] = new pair[n+1]; for(int i = 1; i <= n; i++)pic[i] = new pair(readInt(),readInt());
        Arrays.sort(pic, 1, n+1,new cmp()); 
        for(int i = 1; i <= m; i++){framsz[i] = readInt();} 
        Arrays.sort(framsz,1,m+1);
        int dp[][] = new int[n+1][m+1]; 
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(pic[i].sz <= framsz[j]){
                    dp[i][j] = Math.max(Math.max(dp[i-1][j-1]+1, dp[i-1][j]),dp[i][j-1]);
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        System.out.println(dp[n][m]);
    }

    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine().trim());
        }
        return st.nextToken();
    }

    static long readLong() throws IOException {
        return Long.parseLong(next());
    }

    static int readInt() throws IOException {
        return Integer.parseInt(next());
    }

    static double readDouble() throws IOException {
        return Double.parseDouble(next());
    }

    static char readCharacter() throws IOException {
        return next().charAt(0);
    }

    static String readLine() throws IOException {
        return br.readLine().trim();
    }

    static int upper_bound(ArrayList<Integer> a, int key) {
        int lo = 0, hi = a.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (a.get(mid) == key) {
                lo = mid + 1;
            } else if (a.get(mid) > key) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return hi;
    }

    static int lower_bound(ArrayList<Integer> a, int key) {
        int lo = 0, hi = a.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (a.get(mid) == key) {
                hi = mid - 1;
            } else if (a.get(mid) > key) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }

    static int gcd(int x, int y) {
        return y == 0 ? x : gcd(y, x % y);
    }

    public static long modexponent(long x, long exp, long mod) {
        if (exp == 0) {
            return 1;
        }
        long t = modexponent(x, exp / 2, mod);
        t = (t * t) % mod;
        if (exp % 2 == 0) {
            return t;
        }
        return (t * x % mod) % mod;
    }

    public static boolean next_permutation(int a[]) {
        int n = a.length;
        int p = n - 2;
        int q = n - 1;

        while (p >= 0 && a[p] >= a[p + 1]) {
            p--;
        }
        if (p < 0) {
            return false;
        }

        while (a[q] <= a[p]) {
            q--;
        }
        int t = a[p];
        a[p] = a[q];
        a[q] = t;

        for (int i = p + 1, j = n - 1; i < j; i++, j--) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        return true;
    }

    static long getSubHash(long hash[], long pow[], int l, int r) {
        return hash[r] - hash[l - 1] * pow[r - l + 1];
    }

}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8556 KB Output is correct
2 Correct 75 ms 8528 KB Output is correct
3 Correct 72 ms 8556 KB Output is correct
4 Correct 76 ms 8556 KB Output is correct
5 Correct 76 ms 8808 KB Output is correct
6 Correct 93 ms 8656 KB Output is correct
7 Correct 73 ms 8556 KB Output is correct
8 Correct 74 ms 8556 KB Output is correct
9 Correct 72 ms 8556 KB Output is correct
10 Correct 75 ms 8548 KB Output is correct
11 Correct 75 ms 8696 KB Output is correct
12 Correct 75 ms 8628 KB Output is correct
13 Correct 74 ms 8392 KB Output is correct
14 Correct 74 ms 8556 KB Output is correct
15 Correct 73 ms 8556 KB Output is correct
16 Correct 75 ms 8428 KB Output is correct
17 Correct 73 ms 8540 KB Output is correct
18 Correct 77 ms 8556 KB Output is correct
19 Correct 72 ms 8540 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8556 KB Output is correct
2 Correct 75 ms 8528 KB Output is correct
3 Correct 72 ms 8556 KB Output is correct
4 Correct 76 ms 8556 KB Output is correct
5 Correct 76 ms 8808 KB Output is correct
6 Correct 93 ms 8656 KB Output is correct
7 Correct 73 ms 8556 KB Output is correct
8 Correct 74 ms 8556 KB Output is correct
9 Correct 72 ms 8556 KB Output is correct
10 Correct 75 ms 8548 KB Output is correct
11 Correct 75 ms 8696 KB Output is correct
12 Correct 75 ms 8628 KB Output is correct
13 Correct 74 ms 8392 KB Output is correct
14 Correct 74 ms 8556 KB Output is correct
15 Correct 73 ms 8556 KB Output is correct
16 Correct 75 ms 8428 KB Output is correct
17 Correct 73 ms 8540 KB Output is correct
18 Correct 77 ms 8556 KB Output is correct
19 Correct 72 ms 8540 KB Output is correct
20 Correct 219 ms 17416 KB Output is correct
21 Correct 235 ms 17392 KB Output is correct
22 Correct 219 ms 17376 KB Output is correct
23 Correct 227 ms 17348 KB Output is correct
24 Correct 228 ms 17488 KB Output is correct
25 Correct 233 ms 17248 KB Output is correct
26 Correct 218 ms 17276 KB Output is correct
27 Correct 230 ms 17380 KB Output is correct
28 Correct 227 ms 17248 KB Output is correct
29 Correct 224 ms 17376 KB Output is correct
30 Correct 220 ms 17372 KB Output is correct
31 Correct 219 ms 17524 KB Output is correct
32 Correct 186 ms 12000 KB Output is correct
33 Correct 99 ms 8924 KB Output is correct
34 Correct 231 ms 15092 KB Output is correct
35 Correct 146 ms 10064 KB Output is correct
36 Correct 262 ms 17556 KB Output is correct
37 Correct 223 ms 17456 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8556 KB Output is correct
2 Correct 75 ms 8528 KB Output is correct
3 Correct 72 ms 8556 KB Output is correct
4 Correct 76 ms 8556 KB Output is correct
5 Correct 76 ms 8808 KB Output is correct
6 Correct 93 ms 8656 KB Output is correct
7 Correct 73 ms 8556 KB Output is correct
8 Correct 74 ms 8556 KB Output is correct
9 Correct 72 ms 8556 KB Output is correct
10 Correct 75 ms 8548 KB Output is correct
11 Correct 75 ms 8696 KB Output is correct
12 Correct 75 ms 8628 KB Output is correct
13 Correct 74 ms 8392 KB Output is correct
14 Correct 74 ms 8556 KB Output is correct
15 Correct 73 ms 8556 KB Output is correct
16 Correct 75 ms 8428 KB Output is correct
17 Correct 73 ms 8540 KB Output is correct
18 Correct 77 ms 8556 KB Output is correct
19 Correct 72 ms 8540 KB Output is correct
20 Correct 219 ms 17416 KB Output is correct
21 Correct 235 ms 17392 KB Output is correct
22 Correct 219 ms 17376 KB Output is correct
23 Correct 227 ms 17348 KB Output is correct
24 Correct 228 ms 17488 KB Output is correct
25 Correct 233 ms 17248 KB Output is correct
26 Correct 218 ms 17276 KB Output is correct
27 Correct 230 ms 17380 KB Output is correct
28 Correct 227 ms 17248 KB Output is correct
29 Correct 224 ms 17376 KB Output is correct
30 Correct 220 ms 17372 KB Output is correct
31 Correct 219 ms 17524 KB Output is correct
32 Correct 186 ms 12000 KB Output is correct
33 Correct 99 ms 8924 KB Output is correct
34 Correct 231 ms 15092 KB Output is correct
35 Correct 146 ms 10064 KB Output is correct
36 Correct 262 ms 17556 KB Output is correct
37 Correct 223 ms 17456 KB Output is correct
38 Execution timed out 1100 ms 20056 KB Time limit exceeded
39 Halted 0 ms 0 KB -