Submission #1274751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274751		cngkhanh_ti22	Linear Garden (IOI08_linear_garden)	C++20	8 / 100	152 ms	131072 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 + 2]

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[1000001][5][5][5], res;
//using array => 75% score on oj.uz (MLE on codeforces, depending on the oj, some only counts used array elements)
//oj.uz/problem/view/IOI08_linear_garden
//using vector => 65% score on codeforces
//ioi.contest.codeforces.com/group/32KGsXgiKA/contest/103753/problem/E

/*
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>...
//... with <sumMin> and <sumMax> being the min and max of sum on the way of creating <len> from <len - 1>
int prefix, opt[5];

void updateDp(int l, int r){
    for(int i = l; i <= r; i++){
        for(int s = -1; s <= 2; s++){
            for(int k = max(-2, s - 2); k <= 1; k++){
                for(int j = 0; j <= 2; j++){
                    (dp(i, s, min(k, s - 1), max(j, s - 1)) += dp(i - 1, s - 1, k, j)) %= m;
                }
            }
        }

        for(int s = -2; s <= 1; s++){
            for(int k = 0; k <= min(2, s + 2); k++){
                for(int j = -2; j <= k; j++){
                    (dp(i, s, min(j, s + 1), max(k, s + 1)) += dp(i - 1, s + 1, j, k)) %= m;
                }
            }
        }
    }
}

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;
    dp(1, 1, 0, 0) = 1;
    dp(1, -1, 0, 0) = 1;

    int dpN = 1;

    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
            //opt - nn + j - k <= 2    =>    k >= opt - nn + j - 2
            //opt - ln + j - l >= -2   =>    l <= opt - ln + j + 2

            updateDp(dpN + 1, i + 1);
            dpN = i + 1;

            for(int j = -2; j <= 2; j++){//sum
                for(int k = max(-2, opt - nn + j - 2); k <= 1; k++){//min
                    for(int l = max(-1, k); l <= min(2, opt - ln + j + 2); l++){//max
                        (res += dp(n - i - 1, j, k, l)) %= m;
                    }
                }
            }
        }

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

    cout << (++res) % m;

    return 0;
}

Compilation message (stderr)

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

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