oj.uz

Submission #52085

# Submission time Handle Problem Language Result Execution time Memory
52085 2018-06-23T19:45:55 Z FLDutchman Energetic turtle (IZhO11_turtle) C++14
75 / 100
 2000 ms 1784 KB 
#include "bits/stdc++.h"
using namespace std;

#define fast_io() ios::sync_with_stdio(false)
#define int long long
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define snd second
#define fst first
#define pb push_back

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;

const int NMAX = 300100;

int N, M, K, T, Z;
vi primes;
vii traps;
vi adj[30];

int mod(int n){
    if(n >= 0) return n % Z;
    else return (n%Z) + Z;
}


int expcnt(int n, int p){
    int res = 0;
    while(n){
        n/= p;
        res += n;
    }
    return res;
}

int mpow(int a, int b){
    if(b == 0) return 1;
    if(b & 1) return a*mpow(a*a%Z, b>>1)%Z;
    return mpow(a*a%Z, b>>1); 
}

int C(int a, int b){
    // a! / (b!(a-b)!)
    int res = 1;
    for(int i = 0; primes[i] <= a; i++){
        int ex = expcnt(a, primes[i]) - expcnt(b, primes[i]) - expcnt(a-b, primes[i]);
        res = mod(res * mpow(primes[i], ex));
    }
    return res;
}

int ways(int dx, int dy){
    if(dx < 0 or dy < 0) return 0;
    return C(dx + dy, dx);
}

int dp1[30][30];
// paths from trap a to b passing through no other traps

// a > b
int numPaths(int a, int b){
    int &res = dp1[a][b];
    if(res != -1) return res;
    if(traps[a].fst - traps[b].fst < 0 or traps[a].snd - traps[b].snd < 0) return res = 0;
    res = ways(traps[a].fst - traps[b].fst, traps[a].snd - traps[b].snd);
    //cout << a << " " << b << endl;
    //cout << "sres " <<res <<endl;
    for(int t : adj[a]) if(t!=b){
        int o = mod(ways(traps[a].fst - traps[t].fst, traps[a].snd - traps[t].snd) * numPaths(t, b));
        //cout << a << " " << t << " " << b << endl;
        //cout << "o " << o << " " << ways(traps[a].fst - traps[t].fst, traps[a].snd - traps[t].snd) << " " <<  numPaths(t, b) << endl;
        res -= o;
    }
    //cout << "res " << res << endl;
    res = mod(res);
    return res;
}

int dp2[30][100];

// from trap a to 0, 0 through at least t traps
int f(int a, int t){
    //cout << a << " " << t << endl;
    int &res = dp2[a][t+30];
    if(res != -1) return res;
    if(a == 0){
        return res = (t < 0);
    }
    res = 0;
    for(int k : adj[a]){
        res = mod(res + f(k, t-1) * numPaths(a, k) ); 
    }
    return res;
}

signed main(){
    FOR(i, 0, 30) FOR(j, 0, 30) dp1[i][j] = -1;
    FOR(i, 0, 30) FOR(j, 0, 100) dp2[i][j] = -1;

    fast_io();
    cin >> N >> M >> K >> T >> Z;
    bitset<NMAX*4> isPrime;
    isPrime.set();
    isPrime[0] = isPrime[1] = 0;    
    
    for(int i = 0; i*i < NMAX*4; i++){
        if(isPrime[i])
        for(int j = 2*i; j < NMAX*4; j += i){
            isPrime[j] = 0;
        }
    }
    FOR(i, 0, NMAX*4) if(isPrime[i]) primes.pb(i);
    //cout << C(5, 2) << endl;

    traps.pb({0, 0});
    FOR(i, 0, K) {
        int x, y;
        cin >> x >> y;
        traps.pb({x, y});
    }
    traps.pb({N, M});
    FOR(i, 0, traps.size()) FOR(j, 0, traps.size()){
        if(i != j and traps[i].fst <= traps[j].fst and traps[i].snd <= traps[j].snd){
            adj[j].pb(i);
        }
    }

    /*
    FOR(i, 0, traps.size()) {
        FOR(j, 0, traps.size()){
            numPaths(i, j);
            //cout << << " "; 
        }
        //cout << endl;
    }


    FOR(i, 0, traps.size()) {
        FOR(j, 0, traps.size()){
            cout << numPaths(i, j) << " "; 
        }
        cout << endl;
    }
*/

    //cout << f( (int) traps.size()-1, 0) << endl;
    cout << mod(ways(N, M) - f( (int) traps.size()-1, T+1) ) << endl;
}

Compilation message

turtle.cpp: In function 'int main()':
turtle.cpp:6:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = (l); i < (r); i++)
                                         ^
turtle.cpp:123:5: note: in expansion of macro 'FOR'
     FOR(i, 0, traps.size()) FOR(j, 0, traps.size()){
     ^~~
turtle.cpp:6:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, l, r) for(int i = (l); i < (r); i++)
                                         ^
turtle.cpp:123:29: note: in expansion of macro 'FOR'
     FOR(i, 0, traps.size()) FOR(j, 0, traps.size()){
                             ^~~

Subtask #1
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1652 KB Output is correct
2 Correct 13 ms 1648 KB Output is correct
3 Correct 15 ms 1692 KB Output is correct
4 Correct 16 ms 1652 KB Output is correct
5 Correct 20 ms 1656 KB Output is correct
6 Correct 19 ms 1652 KB Output is correct
7 Correct 23 ms 1652 KB Output is correct
8 Correct 20 ms 1652 KB Output is correct
9 Correct 76 ms 1652 KB Output is correct
10 Correct 107 ms 1696 KB Output is correct
11 Correct 588 ms 1652 KB Output is correct
12 Execution timed out 2008 ms 1652 KB Time limit exceeded
13 Correct 607 ms 1656 KB Output is correct
14 Correct 955 ms 1692 KB Output is correct
15 Correct 1116 ms 1652 KB Output is correct
16 Execution timed out 2029 ms 1652 KB Time limit exceeded
17 Correct 1728 ms 1784 KB Output is correct
18 Execution timed out 2074 ms 1652 KB Time limit exceeded
19 Execution timed out 2077 ms 1704 KB Time limit exceeded
20 Execution timed out 2032 ms 1652 KB Time limit exceeded