| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 94029 | 2019-01-14T21:05:07 Z | zeyad49 | Teams (CEOI11_tea) | Java 11 | 2500 ms | 117556 KB |
import java.io.*;
import java.util.*;
class tea{
static int INF=(int)1e9;
public static void main(String[] args) throws IOException {
Scanner sc=new Scanner();
PrintWriter out=new PrintWriter(System.out);
int n=sc.nextInt();
Integer[]indices=new Integer[n];
int []a=new int [n];
for(int i=0;i<n;i++) {
a[i]=sc.nextInt();
indices[i]=i;
}
Arrays.sort(indices,Comparator.comparingInt(i->-a[i]));
int []dp=new int [n+1]; //number of teams
int []nxt=new int [n+1];
int []maxTeam=new int [n+1];
maxTeam[n]=-INF;
for(int i=n-1;i>=0;i--) {
int idx=indices[i];
if(i+a[idx]>n)
dp[i]=-INF;
else {
int best=i+a[idx];
int currMax=Math.max(a[idx],maxTeam[i+a[idx]]);
for(int j=i+a[idx];j<=n;j++)
{
int newMax=Math.max(j-i,maxTeam[j]);
if(dp[j]>dp[best]||(dp[j]==dp[best] && newMax<currMax)) {
best=j;
currMax=newMax;
}
}
nxt[i]=best;
dp[i]=1+dp[best];
maxTeam[i]=currMax;
}
}
out.println(dp[0]);
Queue<Integer> list=new LinkedList();
for(int i=0;i<n;) {
int j=nxt[i];
while(i<j) {
list.add(indices[i]+1);
i++;
}
out.print(list.size());
while(!list.isEmpty())
out.print(" "+list.poll());
out.println();
}
out.close();
}
static class Scanner
{
BufferedReader br;
StringTokenizer st;
Scanner(){
br=new BufferedReader(new InputStreamReader(System.in));
}
Scanner(String fileName) throws FileNotFoundException{
br=new BufferedReader(new FileReader(fileName));
}
String next() throws IOException {
while(st==null || !st.hasMoreTokens())
st=new StringTokenizer(br.readLine());
return st.nextToken();
}
String nextLine() throws IOException {
return br.readLine();
}
int nextInt() throws IOException{
return Integer.parseInt(next());
}
long nextLong() throws NumberFormatException, IOException {
return Long.parseLong(next());
}
double nextDouble() throws NumberFormatException, IOException {
return Double.parseDouble(next());
}
}
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 175 ms | 15688 KB | Output is correct |
| 2 | Correct | 167 ms | 15052 KB | Output is correct |
| 3 | Correct | 191 ms | 15292 KB | Output is correct |
| 4 | Correct | 183 ms | 15584 KB | Output is correct |
| 5 | Correct | 180 ms | 14964 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 185 ms | 15696 KB | Output is correct |
| 2 | Correct | 181 ms | 15440 KB | Output is correct |
| 3 | Correct | 185 ms | 15380 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 175 ms | 15336 KB | Output is correct |
| 2 | Correct | 189 ms | 15672 KB | Output is correct |
| 3 | Correct | 192 ms | 15632 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 379 ms | 18000 KB | Output is correct |
| 2 | Correct | 337 ms | 17700 KB | Output is correct |
| 3 | Correct | 327 ms | 17908 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 335 ms | 17600 KB | Output is correct |
| 2 | Correct | 379 ms | 17940 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2603 ms | 29404 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2556 ms | 31212 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2587 ms | 75160 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2605 ms | 114500 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Execution timed out | 2630 ms | 117556 KB | Time limit exceeded |
| 2 | Halted | 0 ms | 0 KB | - |