Submission #1275364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275364		cngkhanh_ti22	Linear Garden (IOI08_linear_garden)	C++20	100 / 100	130 ms	9440 KiB

linear_garden

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define dp(a, b, c, d) dpa[a][b + 2][c + 2][d]

template<class T, class P> bool maximize(T &a, P b){ if(a < b) return a = b, true; return false;}
template<class T, class P> bool minimize(T &a, P b){ if(a > b) return a = b, true; return false;}

int n, m;
string s;
int dpa[2][5][3][3], res;
//using array => 70% score (MLE on codeforces, depending on the oj, some only counts used array elements)
//using vector => 60% score
/*
vector<vector<vector<vector<int>>>> dpa;
dpa = vector<vector<vector<vector<int>>>>(n + 1, vector<vector<vector<int>>>(5, vector<vector<int>>(5, vector<int>(5, 0))));
*/

//L = +1, P = -1
//dp[len][sum][sumMin][sumMax] = the number of ways to create <sum> from a string with length <len>...
//IMPROVEMENT: dp[id]... = the number of ways to create <sum> from a string with length <curN>
//... with <sumMin> and <sumMax> being the min and max of sum on the way of creating <len> from <len - 1>

struct state{
    int len, sum, nn, ln;
};
deque<state> skipped;

void findSkipped(){
    int prefix = 0;
    int opt;
    int nn = 0, ln = 0;
    for(int i = 0; i < n; i++){
        opt = prefix - nn + 1; //try to maximize 'L', opt <= 2 meaning 'L' can be used here
        if(opt <= 2 && s[i] != 'L'){ //if not optimised, calculate the number of string skipped
            opt += nn; //opt = prefix with 'L' being added
            skipped.push_front({n - i - 1, opt, nn, ln});
        }


        if(s[i] == 'L') prefix++;
        else prefix--;
        maximize(ln, prefix);
        minimize(nn, prefix);
    }
}

int curN = 0, id = 0;
void calcDp(){
    curN++;
    id ^= 1;
    memset(dpa[id], 0, sizeof(dpa[id]));

    //adding an L
    for(int s = -1; s <= 2; s++){
        for(int k = max(-2, s - 2); k <= 0; k++){
            for(int j = 0; j <= 2; j++){
                (dp(id, s, min(k, s - 1), max(j, s - 1)) += dp(id ^ 1, s - 1, k, j)) %= m;
            }
        }
    }

    //adding a P
    for(int s = -2; s <= 1; s++){
        for(int k = 0; k <= min(2, s + 2); k++){
            for(int j = -2; j <= 0; j++){
                (dp(id, s, min(j, s + 1), max(k, s + 1)) += dp(id ^ 1, s + 1, j, k)) %= m;
            }
        }
    }
}

void solve(){
    int len, opt, nn, ln;
    while(skipped.size()){
        len = skipped.front().len;
        opt = skipped.front().sum;
        nn = skipped.front().nn;
        ln = skipped.front().ln;

        while(curN < len) calcDp();
        //opt - nn + j - k <= 2    =>    k >= opt - nn + j - 2
        //opt - ln + j - l >= -2   =>    l <= opt - ln + j + 2
        for(int j = -2; j <= 2; j++){//sum
            for(int k = max(-2, opt - nn + j - 2); k <= 0; k++){//min
                for(int l = 0; l <= min(2, opt - ln + j + 2); l++){//max
                    (res += dp(id, j, k, l)) %= m;
                }
            }
        }

        skipped.pop_front();
    }
}

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

    if(fopen("main.inp", "r")){
        freopen("main.inp", "r", stdin);
        freopen("main.out", "w", stdout);
    }

    cin >> n >> m;
    cin >> s;

    dp(0, 0, 0, 0) = 1;

    findSkipped();
    solve();

    cout << (++res) % m;

    return 0;
}

Compilation message (stderr)

linear_garden.cpp: In function 'int main()':
linear_garden.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen("main.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
linear_garden.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen("main.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 4 / 4
• Subtask 7: 4 / 4
• Subtask 8: 4 / 4
• Subtask 9: 4 / 4
• Subtask 10: 4 / 4
• Subtask 11: 4 / 4
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5
• Subtask 21: 5 / 5
• Subtask 22: 5 / 5
• Subtask 23: 5 / 5