Untitled

mail@pastecode.io avatar
unknown
java
3 years ago
8.0 kB
22
Indexable
Never
//A


import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Solution {

    static long n1(long[][] dp, int[][] a, int pos, int n, int b) {
        if (n <= pos) {
            return 0;
        }
        if (dp[pos][b] != -1) {
            return dp[pos][b];
        }
        long sum1 = 0;
        if (b == 1) {
            sum1 = n1(dp, a, pos + 1, n, 0) + a[0][pos];
        }
        long sum2 = n1(dp, a, pos + 1, n, 1);
        return dp[pos][b] = Math.max(sum1, sum2);
    }

    static long n2(long[][] dp, int[][] arra, int[][] a, int pos, int n, int b) {
        if (n <= pos) {
            return 0;
        }
        long sum1 = 0;
        long sum2 = 0;
        long sum3 = 0;
        if (dp[pos][b] != -1) {
            return dp[pos][b];
        }
        if (b != a[pos][0]) {
            sum1 = n2(dp, arra, a, pos + 1, n, a[pos][0]) + arra[a[pos][0]][pos];
        }
        if (b != a[pos][1]) {
            sum2 = n2(dp, arra, a, pos + 1, n, a[pos][1]) + arra[a[pos][1]][pos];
        }
        if (b != a[pos][2]) {
            sum3 = n2(dp, arra, a, pos + 1, n, a[pos][2]) + arra[a[pos][2]][pos];
        }

        return dp[pos][b] = Math.max(sum1, Math.max(sum2, sum3));
    }

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        int[][] a = new int[n + 1][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = scan.nextInt();
            }
        }
        a[n][m - 1] = 0;
        if (n == 1) {
            long[][] dp = new long[m + 10][2];
            for (int i = 0; i < m + 10; i++) {
                for (int j = 0; j < 2; j++) {
                    dp[i][j] = -1;
                }
            }
            long on = n1(dp, a, 0, m, 1);
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < 2; j++) {
                    dp[i][j] = -1;
                }
            }
            long tw = n1(dp, a, 0, m, 0);
            System.out.println(Math.max(on, tw));
            return;
        }
        int[][] f = new int[m][3];
        for (int i = 0; i < m; i++) {
            ArrayList<Integer> ar = new ArrayList<Integer>();
            for (int j = 0; j < n; j++) {
                ar.add(a[j][i]);
            }
            Collections.sort(ar);
            int fx = n;
            int fl = n;
            int pl = n;
            int x = ar.get(ar.size() - 1);
            int y = ar.get(ar.size() - 2);
            int z = 0;
            boolean xb = true;
            boolean yb = true;
            boolean zb = true;
            if (n > 2) {
                z = ar.get(ar.size() - 3);
            }
            for (int j = 0; j < n; j++) {
              
                if (x == a[j][i] && xb) {
                    fx = j;
                    xb = false;
                }
                if (y == a[j][i] && j != fx && yb) {
                    fl = j;
                    yb = false;
                }
                if (n > 2) {
                    if (z == a[j][i] && j != fx && j != fl && zb) {
                        pl = j;
                        zb = false;
                    }
                }
            }
            f[i][0] = fx;
            f[i][1] = fl;
            f[i][2] = pl;
        }
        long[][] dp = new long[m + 10][n + 10];
        for (int i = 0; i < m + 10; i++) {
            for (int j = 0; j < n + 10; j++) {
                dp[i][j] = -1;
            }
        }
        long on = n2(dp, a, f, 0, m, f[0][1]);
        for (int i = 0; i < m + 10; i++) {
            for (int j = 0; j < n + 10; j++) {
                dp[i][j] = -1;
            }
        }
        long tw = n2(dp, a, f, 0, m, f[0][0]);

        System.out.println(Math.max(on, tw));

    }
}





//C

import java.util.Scanner;

public class Solution {

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String s = scan.next();
        int[] a = new int[26];
        for (int i = 0; i < s.length(); i++) {
            ++a[s.charAt(i) - 'A'];
        }
        for (int i = 0; i < 26; i++) {
            if (a[i] >= 2) {
                System.out.println("NO");
                return ;
            }
        }
        System.out.println("YES");
    }
}




//D


import java.util.ArrayList;
import java.util.Scanner;

public class Solution {

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String s = scan.next();
        int n = scan.nextInt();
        char[] a = {'l', 'j', '!'};
        char[] b = {'a', '@', 'O', 'o', 'D', '0', 'e'};
        char[] c = {'s', 'S', '5', '2'};
        char[] d = {'1', 'i', '?'};
        ArrayList<Integer> ar = new ArrayList<Integer>();
        k:
        for (int i = 0; i < n; i++) {
            String in = scan.next();
            int e = 0;
            for (int j = 0; j < Math.min(in.length(), s.length()); j++) {
                if (s.charAt(j) != in.charAt(j)) {
                    int tr = 0;
                    for (int k = 0; k < a.length; k++) {
                        if (s.charAt(j) == a[k]) {
                            for (int l = 0; l < a.length; l++) {
                                if (in.charAt(j) == a[l]) {
                                    tr = 1;
                                }
                            }
                        }
                    }

                    for (int k = 0; k < b.length; k++) {
                        if (s.charAt(j) == b[k]) {
                            for (int l = 0; l < b.length; l++) {
                                if (in.charAt(j) == b[l]) {
                                    tr = 1;
                                }
                            }
                        }
                    }

                    for (int k = 0; k < c.length; k++) {
                        if (s.charAt(j) == c[k]) {
                            for (int l = 0; l < c.length; l++) {
                                if (in.charAt(j) == c[l]) {
                                    tr = 1;
                                }
                            }
                        }
                    }

                    for (int k = 0; k < d.length; k++) {
                        if (s.charAt(j) == d[k]) {
                            for (int l = 0; l < d.length; l++) {
                                if (in.charAt(j) == d[l]) {
                                    tr = 1;
                                }
                            }
                        }
                    }
                    if (tr == 0) {
                        ++e;
                    }
                }

            }
            if (e == 0 && s.length() == in.length()) {
                ar.add(i + 1);
            }
        }
        System.out.println(ar.size());
        for (int i = 0; i < ar.size(); i++) {
            System.out.print(ar.get(i) + " ");
        }
        System.out.println();
    }
}



//E

import java.util.Scanner;

public class Solution {

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        String s = scan.next().toLowerCase();
        int c = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'a' || s.charAt(i) == 'e' || s.charAt(i) == 'i' || s.charAt(i) == 'o' || s.charAt(i) == 'u') {
                ++c;
            }
        }
        if (c > 2) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}


//F

import java.util.ArrayList;
import java.util.Scanner;

public class Solution {

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        while (t-- > 0) {
            long n = scan.nextInt();
            long res = (n * (n + 1)) / 2;
            System.out.println(res);
        }
    }
}