Submission #1306427
Source Code Expand
import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { new Main().solve(); } int n; int[]a; int[][] comb; void solve(){ Scanner sc=new Scanner(System.in); n=sc.nextInt(); a=new int[n]; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); } ArrayList<Integer> s=new ArrayList<>(); int cnt=1; int max=0; for(int i=0;i<n-1;i++){ if(a[i]>=a[i+1]){ s.add(cnt); if(max<cnt)max=cnt; cnt=0; } cnt++; if(i==n-2){ s.add(cnt); if(max<cnt)max=cnt; } } comb=new int[max+2][max+2]; make_comb(max+1); int len=s.size(); long sum=0; for(int i=0;i<len;i++){ int m=s.get(i); if(m>1){ sum+=comb[m][2]; } } System.out.println(sum+n); } void make_comb(int N){ for(int i=0;i<=N;i++){ for(int j=0;j<=i;j++){ if(j==0 || i==j)comb[i][j]=1; else{ comb[i][j]=comb[i-1][j]+comb[i-1][j-1]; } } } } }
Submission Info
Submission Time | |
---|---|
Task | C - 単調増加 |
User | kwkm0429 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 40 |
Code Size | 1024 Byte |
Status | MLE |
Exec Time | 1143 ms |
Memory | 1000428 KB |
Judge Result
Set Name | Sample | Subtask0 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 40 / 40 | 0 / 60 | ||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample0.txt, sample1.txt, sample2.txt, sample3.txt |
Subtask0 | sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt |
All | sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample0.txt | AC | 129 ms | 23636 KB |
sample1.txt | AC | 97 ms | 21716 KB |
sample2.txt | AC | 96 ms | 21076 KB |
sample3.txt | AC | 97 ms | 19284 KB |
subtask0_0.txt | AC | 150 ms | 25876 KB |
subtask0_1.txt | AC | 163 ms | 26232 KB |
subtask0_10.txt | AC | 150 ms | 24916 KB |
subtask0_11.txt | AC | 204 ms | 79220 KB |
subtask0_12.txt | AC | 153 ms | 25452 KB |
subtask0_13.txt | AC | 166 ms | 28012 KB |
subtask0_14.txt | AC | 156 ms | 25648 KB |
subtask0_2.txt | AC | 137 ms | 21972 KB |
subtask0_3.txt | AC | 125 ms | 24276 KB |
subtask0_4.txt | AC | 144 ms | 25528 KB |
subtask0_5.txt | AC | 103 ms | 20052 KB |
subtask0_6.txt | AC | 124 ms | 19412 KB |
subtask0_7.txt | AC | 135 ms | 25300 KB |
subtask0_8.txt | AC | 106 ms | 19924 KB |
subtask0_9.txt | AC | 150 ms | 25936 KB |
subtask1_0.txt | AC | 412 ms | 50300 KB |
subtask1_1.txt | MLE | 603 ms | 356340 KB |
subtask1_10.txt | MLE | 1143 ms | 1000428 KB |
subtask1_11.txt | MLE | 971 ms | 852564 KB |
subtask1_12.txt | AC | 427 ms | 51440 KB |
subtask1_13.txt | MLE | 1093 ms | 964508 KB |
subtask1_14.txt | AC | 389 ms | 48940 KB |
subtask1_15.txt | MLE | 1012 ms | 913612 KB |
subtask1_2.txt | AC | 287 ms | 40340 KB |
subtask1_3.txt | AC | 366 ms | 46656 KB |
subtask1_4.txt | MLE | 844 ms | 609476 KB |
subtask1_5.txt | AC | 376 ms | 46916 KB |
subtask1_6.txt | AC | 307 ms | 45836 KB |
subtask1_7.txt | MLE | 712 ms | 311948 KB |
subtask1_8.txt | AC | 270 ms | 42396 KB |
subtask1_9.txt | AC | 213 ms | 33836 KB |