oj.uz

Submission #600743

# Submission time Handle Problem Language Result Execution time Memory
600743 2022-07-21T07:34:31 Z isaachew Uplifting Excursion (BOI22_vault) C++17
5 / 100
 5000 ms 524288 KB 
#include <bits/stdc++.h>
/*
 Lift
 
 ST3-6 are split up into half-subtasks
 
 ST2.5-5.5: simple DP?
 
 5000ms time limit;
 
 20p with brute force O((n/2)^5)
 2:56 pm
 
 ST1/2: plain brute force (O(M*(sum(a_l)^2)) = O(n^5))
 
 */
std::vector<int> uplifts;
int main(){
    int m;
    long long l;
    std::cin>>m>>l;
    int maxv=0;
    for(int i=-m;i<=m;i++){
        int x;
        std::cin>>x;
        uplifts.push_back(x);
        maxv=std::max(x,maxv);
    }
    if(m*m*maxv*maxv<=100000000){
        int tmv=m*(m+1)/2*maxv+1;//really only half of the max
        std::vector<int> values1(tmv,-1000000000);//positive
        std::vector<int> values2(tmv,-1000000000);//negative
        values1[0]=0;
        values2[0]=0;
        for(int k=1;k<=m;k++){
            for(int x=0;x<uplifts[m+k];x++){
                for(int y=tmv-1-k;y>=0;y--){
                    values1[y+k]=std::max(values1[y]+1,values1[y+k]);
                }
            }
        }
        for(int k=1;k<=m;k++){
            for(int x=0;x<uplifts[m-k];x++){
                for(int y=tmv-1-k;y>=0;y--){
                    values2[y+k]=std::max(values2[y]+1,values2[y+k]);
                }
            }
        }
        int totalmax=-1;
        for(int i=0;i<tmv&&i-l<tmv;i++){
            if(i-l<0)continue;
            totalmax=std::max(totalmax,values1[i]+values2[i-l]);
        }
        if(totalmax<0){
            std::cout<<"impossible\n";
        }else{
            std::cout<<totalmax+uplifts[m]<<'\n';
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 148 ms 792 KB Output is correct
6 Correct 188 ms 796 KB Output is correct
7 Correct 61 ms 784 KB Output is correct
8 Correct 164 ms 788 KB Output is correct
9 Correct 280 ms 724 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 9 ms 724 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 148 ms 792 KB Output is correct
6 Correct 188 ms 796 KB Output is correct
7 Correct 61 ms 784 KB Output is correct
8 Correct 164 ms 788 KB Output is correct
9 Correct 280 ms 724 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 9 ms 724 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 176 ms 804 KB Output is correct
17 Correct 216 ms 784 KB Output is correct
18 Correct 99 ms 724 KB Output is correct
19 Correct 201 ms 784 KB Output is correct
20 Correct 270 ms 724 KB Output is correct
21 Correct 6 ms 684 KB Output is correct
22 Correct 9 ms 812 KB Output is correct
23 Correct 4920 ms 4208 KB Output is correct
24 Correct 4919 ms 4252 KB Output is correct
25 Correct 1683 ms 4092 KB Output is correct
26 Execution timed out 5051 ms 4180 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 245 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 245 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 245 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 148 ms 792 KB Output is correct
6 Correct 188 ms 796 KB Output is correct
7 Correct 61 ms 784 KB Output is correct
8 Correct 164 ms 788 KB Output is correct
9 Correct 280 ms 724 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 9 ms 724 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Runtime error 245 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 245 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 148 ms 792 KB Output is correct
6 Correct 188 ms 796 KB Output is correct
7 Correct 61 ms 784 KB Output is correct
8 Correct 164 ms 788 KB Output is correct
9 Correct 280 ms 724 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 9 ms 724 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 176 ms 804 KB Output is correct
17 Correct 216 ms 784 KB Output is correct
18 Correct 99 ms 724 KB Output is correct
19 Correct 201 ms 784 KB Output is correct
20 Correct 270 ms 724 KB Output is correct
21 Correct 6 ms 684 KB Output is correct
22 Correct 9 ms 812 KB Output is correct
23 Correct 4920 ms 4208 KB Output is correct
24 Correct 4919 ms 4252 KB Output is correct
25 Correct 1683 ms 4092 KB Output is correct
26 Execution timed out 5051 ms 4180 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 245 ms 524288 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 148 ms 792 KB Output is correct
6 Correct 188 ms 796 KB Output is correct
7 Correct 61 ms 784 KB Output is correct
8 Correct 164 ms 788 KB Output is correct
9 Correct 280 ms 724 KB Output is correct
10 Correct 7 ms 724 KB Output is correct
11 Correct 9 ms 724 KB Output is correct
12 Correct 1 ms 300 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 176 ms 804 KB Output is correct
17 Correct 216 ms 784 KB Output is correct
18 Correct 99 ms 724 KB Output is correct
19 Correct 201 ms 784 KB Output is correct
20 Correct 270 ms 724 KB Output is correct
21 Correct 6 ms 684 KB Output is correct
22 Correct 9 ms 812 KB Output is correct
23 Correct 4920 ms 4208 KB Output is correct
24 Correct 4919 ms 4252 KB Output is correct
25 Correct 1683 ms 4092 KB Output is correct
26 Execution timed out 5051 ms 4180 KB Time limit exceeded
27 Halted 0 ms 0 KB -