oj.uz

Submission #697140

# Submission time Handle Problem Language Result Execution time Memory
697140 2023-02-08T15:42:33 Z Jarif_Rahman Snake Escaping (JOI18_snake_escaping) C++17
12 / 100
 234 ms 65536 KB 
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const int p3[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int L, Q; cin >> L >> Q;
    vector<int> v;
    for(int i = 0; i < (1<<L); i++){
        char c; cin >> c; c-='0';
        v.pb(c);
    }

    vector<vector<int>> dp(p3[L], vector<int>(L+1, 0));
    for(int i = 0; i < (1<<L); i++){
        int x = 0;
        for(int j = 0; j < L; j++) if(i&(1<<j)) x+=p3[j];
        dp[x][0]+=v[i];
    }

    for(int i = 0; i < p3[L]; i++) for(int j = 1; j <= L; j++){
        int x = (i/p3[j-1])%3;
        if(x < 2)
            dp[i][j] = dp[i][j-1];
        else
            dp[i][j] = dp[i-p3[j-1]*2][j-1]+dp[i-p3[j-1]][j-1];
    }

    while(Q--){
        str s; cin >> s;
        reverse(s.begin(), s.end());
        int x = 0;
        for(int i = 0; i < L; i++){
            if(s[i] == '?') x+=p3[i]*2;
            else x+=(s[i]-'0')*p3[i];
        }
        cout << dp[x][L] << "\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5332 KB Output is correct
2 Correct 11 ms 5432 KB Output is correct
3 Correct 8 ms 5308 KB Output is correct
4 Correct 11 ms 5320 KB Output is correct
5 Correct 9 ms 5332 KB Output is correct
6 Correct 9 ms 5432 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 8 ms 5332 KB Output is correct
9 Correct 9 ms 5332 KB Output is correct
10 Correct 9 ms 5320 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5332 KB Output is correct
2 Correct 11 ms 5432 KB Output is correct
3 Correct 8 ms 5308 KB Output is correct
4 Correct 11 ms 5320 KB Output is correct
5 Correct 9 ms 5332 KB Output is correct
6 Correct 9 ms 5432 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 8 ms 5332 KB Output is correct
9 Correct 9 ms 5332 KB Output is correct
10 Correct 9 ms 5320 KB Output is correct
11 Correct 221 ms 20220 KB Output is correct
12 Correct 233 ms 19744 KB Output is correct
13 Correct 203 ms 19032 KB Output is correct
14 Correct 194 ms 19116 KB Output is correct
15 Correct 230 ms 20152 KB Output is correct
16 Correct 226 ms 19276 KB Output is correct
17 Correct 234 ms 19300 KB Output is correct
18 Correct 163 ms 21168 KB Output is correct
19 Correct 156 ms 18132 KB Output is correct
20 Correct 200 ms 19800 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5332 KB Output is correct
2 Correct 11 ms 5432 KB Output is correct
3 Correct 8 ms 5308 KB Output is correct
4 Correct 11 ms 5320 KB Output is correct
5 Correct 9 ms 5332 KB Output is correct
6 Correct 9 ms 5432 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 8 ms 5332 KB Output is correct
9 Correct 9 ms 5332 KB Output is correct
10 Correct 9 ms 5320 KB Output is correct
11 Correct 221 ms 20220 KB Output is correct
12 Correct 233 ms 19744 KB Output is correct
13 Correct 203 ms 19032 KB Output is correct
14 Correct 194 ms 19116 KB Output is correct
15 Correct 230 ms 20152 KB Output is correct
16 Correct 226 ms 19276 KB Output is correct
17 Correct 234 ms 19300 KB Output is correct
18 Correct 163 ms 21168 KB Output is correct
19 Correct 156 ms 18132 KB Output is correct
20 Correct 200 ms 19800 KB Output is correct
21 Runtime error 50 ms 65536 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5332 KB Output is correct
2 Correct 11 ms 5432 KB Output is correct
3 Correct 8 ms 5308 KB Output is correct
4 Correct 11 ms 5320 KB Output is correct
5 Correct 9 ms 5332 KB Output is correct
6 Correct 9 ms 5432 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 8 ms 5332 KB Output is correct
9 Correct 9 ms 5332 KB Output is correct
10 Correct 9 ms 5320 KB Output is correct
11 Runtime error 23 ms 10324 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5332 KB Output is correct
2 Correct 11 ms 5432 KB Output is correct
3 Correct 8 ms 5308 KB Output is correct
4 Correct 11 ms 5320 KB Output is correct
5 Correct 9 ms 5332 KB Output is correct
6 Correct 9 ms 5432 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 8 ms 5332 KB Output is correct
9 Correct 9 ms 5332 KB Output is correct
10 Correct 9 ms 5320 KB Output is correct
11 Correct 221 ms 20220 KB Output is correct
12 Correct 233 ms 19744 KB Output is correct
13 Correct 203 ms 19032 KB Output is correct
14 Correct 194 ms 19116 KB Output is correct
15 Correct 230 ms 20152 KB Output is correct
16 Correct 226 ms 19276 KB Output is correct
17 Correct 234 ms 19300 KB Output is correct
18 Correct 163 ms 21168 KB Output is correct
19 Correct 156 ms 18132 KB Output is correct
20 Correct 200 ms 19800 KB Output is correct
21 Runtime error 50 ms 65536 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -