Submission #1005363
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 | 1200 |
Code Size | 12668 Byte |
Status | AC |
Exec Time | 573 ms |
Memory | 39372 KB |
Judge Result
Set Name | Sample | subtask1 | subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 200 / 200 | 800 / 800 | 200 / 200 | ||||||||
Status |
|
|
|
|
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 | 23 ms | 2976 KB |
hack_2.txt | AC | 22 ms | 2848 KB |
hack_3.txt | AC | 22 ms | 2852 KB |
hack_4.txt | AC | 22 ms | 2852 KB |
hack_5.txt | AC | 22 ms | 2852 KB |
sample_1.txt | AC | 22 ms | 2852 KB |
sample_2.txt | AC | 22 ms | 2848 KB |
sample_3.txt | AC | 22 ms | 2848 KB |
subtask_1_1.txt | AC | 22 ms | 2976 KB |
subtask_1_10.txt | AC | 22 ms | 2980 KB |
subtask_1_11.txt | AC | 522 ms | 33024 KB |
subtask_1_12.txt | AC | 23 ms | 3104 KB |
subtask_1_13.txt | AC | 23 ms | 3232 KB |
subtask_1_14.txt | AC | 22 ms | 2848 KB |
subtask_1_15.txt | AC | 537 ms | 34280 KB |
subtask_1_16.txt | AC | 560 ms | 34280 KB |
subtask_1_17.txt | AC | 563 ms | 34152 KB |
subtask_1_18.txt | AC | 539 ms | 34416 KB |
subtask_1_19.txt | AC | 22 ms | 2848 KB |
subtask_1_2.txt | AC | 22 ms | 2852 KB |
subtask_1_20.txt | AC | 22 ms | 3104 KB |
subtask_1_3.txt | AC | 22 ms | 2976 KB |
subtask_1_4.txt | AC | 22 ms | 3104 KB |
subtask_1_5.txt | AC | 24 ms | 3360 KB |
subtask_1_6.txt | AC | 24 ms | 3488 KB |
subtask_1_7.txt | AC | 25 ms | 3616 KB |
subtask_1_8.txt | AC | 523 ms | 34288 KB |
subtask_1_9.txt | AC | 153 ms | 11176 KB |
subtask_2_1.txt | AC | 50 ms | 7896 KB |
subtask_2_10.txt | AC | 68 ms | 8528 KB |
subtask_2_11.txt | AC | 352 ms | 32776 KB |
subtask_2_12.txt | AC | 349 ms | 32776 KB |
subtask_2_13.txt | AC | 343 ms | 39372 KB |
subtask_2_14.txt | AC | 347 ms | 32776 KB |
subtask_2_15.txt | AC | 23 ms | 3104 KB |
subtask_2_16.txt | AC | 340 ms | 32776 KB |
subtask_2_17.txt | AC | 341 ms | 32776 KB |
subtask_2_18.txt | AC | 350 ms | 36036 KB |
subtask_2_19.txt | AC | 23 ms | 3104 KB |
subtask_2_2.txt | AC | 329 ms | 34652 KB |
subtask_2_20.txt | AC | 22 ms | 2976 KB |
subtask_2_21.txt | AC | 23 ms | 2976 KB |
subtask_2_22.txt | AC | 22 ms | 2980 KB |
subtask_2_23.txt | AC | 23 ms | 2976 KB |
subtask_2_24.txt | AC | 23 ms | 2980 KB |
subtask_2_25.txt | AC | 22 ms | 2976 KB |
subtask_2_26.txt | AC | 23 ms | 3104 KB |
subtask_2_27.txt | AC | 23 ms | 3104 KB |
subtask_2_3.txt | AC | 322 ms | 33328 KB |
subtask_2_4.txt | AC | 179 ms | 25280 KB |
subtask_2_5.txt | AC | 349 ms | 32776 KB |
subtask_2_6.txt | AC | 352 ms | 32776 KB |
subtask_2_7.txt | AC | 148 ms | 25156 KB |
subtask_2_8.txt | AC | 37 ms | 6048 KB |
subtask_2_9.txt | AC | 79 ms | 8912 KB |
subtask_3_1.txt | AC | 23 ms | 3232 KB |
subtask_3_10.txt | AC | 567 ms | 34268 KB |
subtask_3_11.txt | AC | 561 ms | 34160 KB |
subtask_3_12.txt | AC | 562 ms | 34152 KB |
subtask_3_13.txt | AC | 22 ms | 3108 KB |
subtask_3_14.txt | AC | 22 ms | 3104 KB |
subtask_3_2.txt | AC | 25 ms | 3488 KB |
subtask_3_3.txt | AC | 572 ms | 34272 KB |
subtask_3_4.txt | AC | 572 ms | 34280 KB |
subtask_3_5.txt | AC | 573 ms | 35352 KB |
subtask_3_6.txt | AC | 572 ms | 34152 KB |
subtask_3_7.txt | AC | 511 ms | 35248 KB |
subtask_3_8.txt | AC | 569 ms | 37912 KB |
subtask_3_9.txt | AC | 569 ms | 35356 KB |