Submission #1306429
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]=Integer.parseInt(sc.next()); } 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 | 1039 Byte |
Status | MLE |
Exec Time | 1038 ms |
Memory | 1000188 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 | 96 ms | 21716 KB |
sample1.txt | AC | 98 ms | 20564 KB |
sample2.txt | AC | 103 ms | 21204 KB |
sample3.txt | AC | 97 ms | 21716 KB |
subtask0_0.txt | AC | 141 ms | 23892 KB |
subtask0_1.txt | AC | 148 ms | 25684 KB |
subtask0_10.txt | AC | 147 ms | 26836 KB |
subtask0_11.txt | AC | 215 ms | 81108 KB |
subtask0_12.txt | AC | 144 ms | 24532 KB |
subtask0_13.txt | AC | 153 ms | 27348 KB |
subtask0_14.txt | AC | 139 ms | 22612 KB |
subtask0_2.txt | AC | 127 ms | 22100 KB |
subtask0_3.txt | AC | 117 ms | 23508 KB |
subtask0_4.txt | AC | 144 ms | 24020 KB |
subtask0_5.txt | AC | 103 ms | 21972 KB |
subtask0_6.txt | AC | 107 ms | 21076 KB |
subtask0_7.txt | AC | 122 ms | 24148 KB |
subtask0_8.txt | AC | 103 ms | 21844 KB |
subtask0_9.txt | AC | 128 ms | 22356 KB |
subtask1_0.txt | AC | 336 ms | 42772 KB |
subtask1_1.txt | MLE | 550 ms | 331284 KB |
subtask1_10.txt | MLE | 1038 ms | 1000188 KB |
subtask1_11.txt | MLE | 972 ms | 909296 KB |
subtask1_12.txt | AC | 388 ms | 48908 KB |
subtask1_13.txt | MLE | 1027 ms | 985124 KB |
subtask1_14.txt | AC | 344 ms | 48440 KB |
subtask1_15.txt | MLE | 996 ms | 949420 KB |
subtask1_2.txt | AC | 232 ms | 36632 KB |
subtask1_3.txt | AC | 307 ms | 41984 KB |
subtask1_4.txt | MLE | 763 ms | 482236 KB |
subtask1_5.txt | AC | 331 ms | 41424 KB |
subtask1_6.txt | AC | 251 ms | 39700 KB |
subtask1_7.txt | MLE | 657 ms | 349880 KB |
subtask1_8.txt | AC | 217 ms | 32836 KB |
subtask1_9.txt | AC | 174 ms | 27648 KB |