oj.uz

Submission #854004

# Submission time Handle Problem Language Result Execution time Memory
854004 2023-09-25T19:33:17 Z divad Lucky Numbers (RMI19_lucky) C++14
28 / 100
 200 ms 1112 KB 
#include <bits/stdc++.h>
#define EQ 0
#define LE 1
using namespace std;
const int MOD = 1e9+7;
const int NMAX = 1e4+2;
const int SIGMA = 10;
int n,q,t,l,r,pos,val,dp[2][SIGMA][NMAX];
string str;

int countWays(int st, int dr){
    dp[EQ][0][0] = 1;
    for(int i = 1; i <= (dr-st+1); i++){
        int pos = i+st-1;
        for(int dig = 0; dig <= 9; dig++){
            dp[EQ][dig][i] = dp[LE][dig][i] = 0;
            for(int lst = 0; lst <= 9; lst++){
                if(lst == 1 && dig == 3){
                    continue;
                }
                if(dig == str[pos]-'0'){
                    dp[EQ][dig][i] += dp[EQ][lst][i-1];
                }
                if(dig <  str[pos]-'0'){
                    dp[LE][dig][i] += dp[EQ][lst][i-1];
                }
                dp[LE][dig][i] += dp[LE][lst][i-1];

                dp[EQ][dig][i] %= MOD;
                dp[LE][dig][i] %= MOD;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i <= 9; i++){
        ans += dp[LE][i][(dr-st+1)] + dp[EQ][i][(dr-st+1)];
        ans %= MOD;
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    cin >> str;
    str = "$"+str;
    cout << countWays(1, n) << "\n";
    while(q--){
        cin >> t;
        if(t == 1){
            cin >> l >> r;
            cout << countWays(l, r) << "\n";
        }else{
            cin >> pos >> val;
            str[pos] = (val+'0');
        }
    }
    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 1112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 1112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Execution timed out 1044 ms 1112 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Execution timed out 1044 ms 1112 KB Time limit exceeded
8 Halted 0 ms 0 KB -