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 |
|
|
|
|
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 |