Submission #1005356


Source Code Expand

using System;
using System.Text;
using System.Collections.Generic;
class Solve{
    int N,M;
    long[,] A;
    public Solve(){}
    StringBuilder sb;
    public static int Main(){
        new Solve().Run();
        return 0;
    }
    void Run(){
        sb = new StringBuilder();
        Read();
        Calc();
        Console.Write(sb.ToString());
    }
    void Calc(){
        long count = 0;
        long b = 0;
        if(M == 1){
            for(int i=1;i<N;i++){
                if(A[i,0] < A[i-1,0]){
                    count = -1;
                    break;
                }
            }
        }
        else{
            for(int i=1;i<N;i++){
                if(A[i,0] > A[i-1,0]){
                    b = 0;
                    continue;
                }
                else if(A[i,0] < A[i-1,0]){
                    count = -1;
                    break;
                }
                else{
                    long c;
                    if(A[i,1] > A[i-1,1]){
                        c = (A[i,1] - A[i-1,1] - 1)/A[i-1,0] + 1;
                        if(c > b){
                            b = 0;
                        }
                        else if(c * A[i-1,0] != A[i,1] - A[i-1,1]){
                            count += b - c + 1;
                            b -= c - 1;
                        }
                        else{
                            //if(c < 30){
                                long[] temp1 = new long[M];
                                long[] temp2 = new long[M];
                                int j = 1;
                                for(int k=0;k<M;k++){
                                    if(k == 0){
                                        temp2[k] = A[i-1,0];
                                    }
                                    else{
                                        temp2[k] = A[i-1,k] + temp2[k-1];
                                    }
                                }
                                for(;j<c;j++){
                                    if(j%2 == 1){
                                        for(int k=0;k<M;k++){
                                            if(k == 0){
                                                temp1[k] = temp2[k];
                                            }
                                            else{
                                                temp1[k] = temp1[k-1] + temp2[k];
                                            }
                                        }
                                    }
                                    else{
                                        for(int k=0;k<M;k++){
                                            if(k == 0){
                                                temp2[k] = temp1[k];
                                            }
                                            else{
                                                temp2[k] = temp2[k-1] + temp1[k];
                                            }
                                        }
                                    }
                                }
                                if(c%2 == 0){
                                    for(int k=0;k<M;k++){
                                        if(temp1[k] > A[i,k]){
                                            break;
                                        }
                                        else if(temp1[k] < A[i,k]){
                                            c++;
                                            break;
                                        }
                                    }
                                }
                                else{
                                    for(int k=0;k<M;k++){
                                        if(temp2[k] > A[i,k]){
                                            break;
                                        }
                                        else if(temp2[k] < A[i,k]){
                                            c++;
                                            break;
                                        }
                                    }
                                }
                            //}
                            /*else{
                                Conv co = new Conv(M,c-1);
                                for(int k=0;k<M;k++){
                                    long sum = 0;
                                    for(int j=0;j<=k;j++){
                                        long x = co.C(k-j);
                                        if(x == -1){
                                            sum = -1;
                                            break;
                                        }
                                        sum += x * A[i-1,j];
                                        if(sum > 1000000000){
                                            sum = -1;
                                            break;
                                        }
                                    }
                                    if(sum == -1 || sum > A[i,k]){
                                        break;
                                    }
                                    else if(sum < A[i,k]){
                                        c++;
                                        break;
                                    }
                                }
                            }*/
                            if(c > b){
                                b = 0;
                            }
                            else{
                                b -= c - 1;
                                count += b;
                            }
                        }
                    }
                    else if(A[i,1] < A[i-1,1]){
                        c = (A[i-1,1] - A[i,1] - 1)/A[i,0] + 1;
                        if(c * A[i,0] != A[i-1,1] - A[i,1]){
                            b += c;
                            count += b;
                        }
                        else{
                            //if(c < 30){
                                long[] temp1 = new long[M];
                                long[] temp2 = new long[M];
                                int j = 1;
                                for(int k=0;k<M;k++){
                                    if(k == 0){
                                        temp2[k] = A[i,0];
                                    }
                                    else{
                                        temp2[k] = A[i,k] + temp2[k-1];
                                    }
                                }
                                for(;j<c;j++){
                                    if(j%2 == 1){
                                        for(int k=0;k<M;k++){
                                            if(k == 0){
                                                temp1[k] = temp2[k];
                                            }
                                            else{
                                                temp1[k] = temp1[k-1] + temp2[k];
                                            }
                                        }
                                    }
                                    else{
                                        for(int k=0;k<M;k++){
                                            if(k == 0){
                                                temp2[k] = temp1[k];
                                            }
                                            else{
                                                temp2[k] = temp2[k-1] + temp1[k];
                                            }
                                        }
                                    }
                                }
                                if(c%2 == 0){
                                    int k;
                                    for(k=0;k<M;k++){
                                        if(temp1[k] > A[i-1,k]){
                                            break;
                                        }
                                        else if(temp1[k] < A[i-1,k]){
                                            c++;
                                            break;
                                        }
                                    }
                                    if(k == M){
                                        c++;
                                    }
                                }
                                else{
                                    int k;
                                    for(k=0;k<M;k++){
                                        if(temp2[k] > A[i-1,k]){
                                            break;
                                        }
                                        else if(temp2[k] < A[i-1,k]){
                                            c++;
                                            break;
                                        }
                                    }
                                    if(k == M){
                                        c++;
                                    }
                                }
                            //}
                            /*else{
                                Conv co = new Conv(M,c-1);
                                int k;
                                for(k=0;k<M;k++){
                                    long sum = 0;
                                    for(int j=0;j<=k;j++){
                                        long x = co.C(k-j);
                                        if(x == -1){
                                            sum = -1;
                                            break;
                                        }
                                        sum += x * A[i,j];
                                        if(sum > 1000000000){
                                            sum = -1;
                                            break;
                                        }
                                    }
                                    if(sum == -1 || sum > A[i-1,k]){
                                        break;
                                    }
                                    else if(sum < A[i-1,k]){
                                        c++;
                                        break;
                                    }
                                }
                                if(k == M){
                                    c++;
                                }
                            }*/
                            b += c;
                            count += b;
                        }
                    }
                    else{
                        int j;
                        for(j=1;j<M;j++){
                            if(A[i-1,j] < A[i,j]){
                                count += b;
                                break;
                            }
                            else if(A[i-1,j] > A[i,j]){
                                b++;
                                count += b;
                                break;
                            }
                        }
                        if(j == M){
                            b++;
                            count += b;
                        }
                    }
                }
            }
        }
        sb.Append(count+"\n");
    }
    void Read(){
        string[] str = Console.ReadLine().Split(' ');
        N = int.Parse(str[0]);
        M = int.Parse(str[1]);
        A = new long[N,M];
        for(int i=0;i<N;i++){
            str = Console.ReadLine().Split(' ');
            for(int j=0;j<M;j++){
                A[i,j] = Int64.Parse(str[j]);
            }
        }
    }    
}
class Conv{
    public int n;
    public long m;
    public long[] c;
    public Conv(int n0,long m0){
        n = n0;
        m = m0;
        c = new long[n];
        for(int i=0;i<n;i++){
            if(i == 0){
                c[i] = 1;
            }
            else{
                c[i] = c[i-1]*(m+i)/i;
                if(c[i] > 1000000000){
                    c[i] = -1;
                    break;
                }
            }
        }
    }
    public long C(int N){
        return c[N];
    }
}

Submission Info

Submission Time
Task B - Takahashi the Magician
User leign
Language C# (Mono 4.6.2.0)
Score 200
Code Size 12683 Byte
Status WA
Exec Time 2105 ms
Memory 43256 KB

Judge Result

Set Name Sample subtask1 subtask2 All
Score / Max Score 0 / 0 200 / 200 0 / 800 0 / 200
Status
AC × 3
AC × 27
AC × 34
WA × 1
AC × 64
WA × 2
TLE × 3
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt
subtask1 sample_1.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
subtask2 sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt
All sample_1.txt, sample_2.txt, sample_3.txt, hack_1.txt, hack_2.txt, hack_3.txt, hack_4.txt, hack_5.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_10.txt, subtask_2_11.txt, subtask_2_12.txt, subtask_2_13.txt, subtask_2_14.txt, subtask_2_15.txt, subtask_2_16.txt, subtask_2_17.txt, subtask_2_18.txt, subtask_2_19.txt, subtask_2_2.txt, subtask_2_20.txt, subtask_2_21.txt, subtask_2_22.txt, subtask_2_23.txt, subtask_2_24.txt, subtask_2_25.txt, subtask_2_26.txt, subtask_2_27.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_2_9.txt, subtask_3_1.txt, subtask_3_10.txt, subtask_3_11.txt, subtask_3_12.txt, subtask_3_13.txt, subtask_3_14.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt, subtask_3_9.txt
Case Name Status Exec Time Memory
hack_1.txt AC 22 ms 2904 KB
hack_2.txt AC 21 ms 2904 KB
hack_3.txt AC 21 ms 2904 KB
hack_4.txt AC 21 ms 2904 KB
hack_5.txt AC 21 ms 2904 KB
sample_1.txt AC 21 ms 2904 KB
sample_2.txt AC 21 ms 2904 KB
sample_3.txt AC 21 ms 2904 KB
subtask_1_1.txt AC 21 ms 3032 KB
subtask_1_10.txt AC 21 ms 3032 KB
subtask_1_11.txt AC 509 ms 33024 KB
subtask_1_12.txt AC 23 ms 3264 KB
subtask_1_13.txt AC 22 ms 3288 KB
subtask_1_14.txt AC 22 ms 2904 KB
subtask_1_15.txt AC 531 ms 34280 KB
subtask_1_16.txt AC 550 ms 34280 KB
subtask_1_17.txt AC 548 ms 34152 KB
subtask_1_18.txt AC 528 ms 34416 KB
subtask_1_19.txt AC 22 ms 3032 KB
subtask_1_2.txt AC 21 ms 3032 KB
subtask_1_20.txt AC 22 ms 3160 KB
subtask_1_3.txt AC 22 ms 3032 KB
subtask_1_4.txt AC 22 ms 3160 KB
subtask_1_5.txt AC 23 ms 3416 KB
subtask_1_6.txt AC 24 ms 3672 KB
subtask_1_7.txt AC 25 ms 3736 KB
subtask_1_8.txt AC 514 ms 34288 KB
subtask_1_9.txt AC 151 ms 11048 KB
subtask_2_1.txt AC 48 ms 7768 KB
subtask_2_10.txt AC 67 ms 8400 KB
subtask_2_11.txt AC 343 ms 32776 KB
subtask_2_12.txt AC 340 ms 32776 KB
subtask_2_13.txt AC 334 ms 39424 KB
subtask_2_14.txt AC 347 ms 32776 KB
subtask_2_15.txt AC 22 ms 3160 KB
subtask_2_16.txt AC 335 ms 32776 KB
subtask_2_17.txt AC 334 ms 32776 KB
subtask_2_18.txt AC 582 ms 43256 KB
subtask_2_19.txt WA 22 ms 3160 KB
subtask_2_2.txt AC 315 ms 34704 KB
subtask_2_20.txt AC 22 ms 3032 KB
subtask_2_21.txt AC 22 ms 3032 KB
subtask_2_22.txt AC 22 ms 3136 KB
subtask_2_23.txt AC 22 ms 3032 KB
subtask_2_24.txt AC 22 ms 3032 KB
subtask_2_25.txt AC 21 ms 3032 KB
subtask_2_26.txt AC 23 ms 3160 KB
subtask_2_27.txt AC 23 ms 3244 KB
subtask_2_3.txt AC 317 ms 33328 KB
subtask_2_4.txt AC 173 ms 25152 KB
subtask_2_5.txt AC 343 ms 32776 KB
subtask_2_6.txt AC 341 ms 32776 KB
subtask_2_7.txt AC 145 ms 25164 KB
subtask_2_8.txt AC 38 ms 6104 KB
subtask_2_9.txt AC 77 ms 8912 KB
subtask_3_1.txt AC 23 ms 3288 KB
subtask_3_10.txt AC 553 ms 34152 KB
subtask_3_11.txt AC 539 ms 34280 KB
subtask_3_12.txt AC 548 ms 34152 KB
subtask_3_13.txt AC 22 ms 3160 KB
subtask_3_14.txt WA 22 ms 3160 KB
subtask_3_2.txt AC 24 ms 3544 KB
subtask_3_3.txt AC 559 ms 34280 KB
subtask_3_4.txt TLE 2104 ms 34280 KB
subtask_3_5.txt TLE 2105 ms 34280 KB
subtask_3_6.txt AC 551 ms 34152 KB
subtask_3_7.txt AC 486 ms 35304 KB
subtask_3_8.txt AC 553 ms 38220 KB
subtask_3_9.txt TLE 2105 ms 34152 KB