Submission #335282

#	Time	Username	Problem	Language	Result	Execution time	Memory
335282		limabeans	Energetic turtle (IZhO11_turtle)	C++17	40 / 100	2103 ms	262144 KiB

turtle

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1010;


ll n,m,k,t,mod;

ll dp[maxn][maxn][22];
bool bad[maxn][maxn];


void add(ll &x, ll y) {
    x %= mod;
    y %= mod;
    x += y;
    x %= mod;
}

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

    cin>>n>>m>>k>>t>>mod;

    while (k--) {
	int x,y;
	cin>>x>>y;
	bad[x][y]=1;
    }

    dp[0][0][t]=1;

    for (int i=0; i<=n; i++) {
	for (int j=0; j<=m; j++) {
	    for (int q=t; q>=(bad[i][j]?1:0); q--) {
		add(dp[i+1][j][q-bad[i][j]], dp[i][j][q]);
		add(dp[i][j+1][q-bad[i][j]], dp[i][j][q]);
	    }
	}
    }

    ll res=0;
    for (int q=0; q<=t; q++) {
	add(res,dp[n][m][q]);
    }

    cout<<res<<endl;    
    return 0;
}

• Subtask 1: 40 / 100