Submission #522588

#	Time	Username	Problem	Language	Result	Execution time	Memory
522588		Leo121	Linear Garden (IOI08_linear_garden)	C++14	100 / 100	145 ms	10092 KiB

linear_garden

#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int lim = 1e6;
int dp[2][5][5];
int pfmin[lim + 2];
int pfmax[lim + 2];
char cadena[lim + 2];
int m, n;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    forn(i, 1, n){
        cin >> cadena[i];
    }
    pfmin[0] = 2;
    pfmax[0] = 1;
    pfmax[1] = (cadena[1] == 'P') ? 3 : 1;
    pfmin[1] = pfmax[1];
    int numero, suma;
    ///cout << "1 : " << pfmin[1] << " " << pfmax[1] << "\n";
    forn(i, 2, n){
        suma = (cadena[i] == 'P') ? 1 : -1;
        numero = (cadena[i] == 'P') ? 3 : 1;
        pfmax[i] = max(pfmax[i - 1] + suma, numero);
        pfmin[i] = min(pfmin[i - 1] + suma, numero);
        ///cout << i << " : " << pfmin[i] << " " << pfmax[i] << "\n";
    }
    forn(i, 0, 4){
        forn(j, i, 4){
            dp[n % 2][i][j] = 1;
            dp[n % 2][i][j] %= m;
        }
    }
    int res = 1;
    res %= m;
    if(cadena[n] == 'P' && min(pfmin[n - 1] - 1, 1) >= 0){
        res += dp[n % 2][min(pfmin[n - 1] - 1, 1)][max(pfmax[n - 1] - 1, 1)];
        res %= m;
    }
    fora(i, n - 1, 1){
        forn(j, 0, 4){
            forn(k, 0, 4){
                ///aniadir P
                dp[i % 2][j][k] = (max(k + 1, 3) > 4) ? 0 : dp[(i - 1) % 2][min(j + 1, 3)][max(k + 1, 3)];
                ///aniadir L
                if(min(j - 1, 1) >= 0) dp[i % 2][j][k] += dp[(i - 1) % 2][min(j - 1, 1)][max(k - 1, 1)];
                dp[i % 2][j][k] %= m;
            }
        }
        if(cadena[i] == 'P' && min(pfmin[i - 1] - 1, 1) >= 0){
            res += dp[i % 2][min(pfmin[i - 1] - 1, 1)][max(pfmax[i - 1] - 1, 1)];
            res %= m;
        }
    }
    cout << res;
	return 0;
}

• 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