oj.uz

Submission #81745

# Submission time Handle Problem Language Result Execution time Memory
81745 2018-10-26T12:13:13 Z Saboon Kangaroo (CEOI16_kangaroo) C++14
36 / 100
 2000 ms 103540 KB 
#include <iostream>
#include <sstream>
#include <queue>
#include <stack>
#include <vector>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iomanip>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int maxn = 2000 + 37;
const int mod = 1e9 + 7;

ll dp[maxn][maxn][3];

ll fen[maxn + 100][maxn][3];

ll get (int idx, int w, int d) {
    if (idx < 0)
        return 0;
    ll ret = 0;
    for (; idx; idx -= idx & -idx)
        ret = (ret + fen[idx][w][d]) % mod;
    return ret;
}

ll sum (int l, int r, int w, int d) {
    return (get (r - 1, w, d) - get (l - 1, w, d) + mod) % mod;
}

void change (int idx, ll val, int w, bool d) {
    for (; idx < maxn; idx += idx & -idx)
        fen[idx][w][d] = (fen[idx][w][d] + val) % mod;
}

int main() {
    ios_base::sync_with_stdio(false);
    int n, s, t;
    cin >> n >> s >> t;
    change (1, 1, 2, 1);
    change (2, 1, 1, 0);
    for (int i = 3; i <= n; i++) {
        for (int st = 1; st <= i; st ++) {
            for (int en = 1; en <= i; en ++) {
                if (st != en) {
                    if (en > st) {
                        dp[st][en][1] = sum (st, i, en - 1, 0);
//                      dp[i][st][en][1] = (dp[i][st][en][1] + par[i - 1][i - 1][en - 1][0] - par[i - 1][st - 1][en - 1][0] + mod + mod) % mod;
                        dp[st][en][0] = sum (0, st, en - 1, 1);
//                      dp[i][st][en][0] = (dp[i][st][en][0] + par[i - 1][st - 1][en - 1][1]) % mod;
                    }
                    else {
                        dp[st][en][1] = sum (st, i, en, 0);
//                      dp[i][st][en][1] = (dp[i][st][en][1] + par[i - 1][i - 1][en][0] - par[i - 1][st - 1][en][0] + mod + mod) % mod;
                        dp[st][en][0] = sum (0, st, en, 1);
//                      dp[i][st][en][0] = (dp[i][st][en][0] + par[i - 1][st - 1][en][1] + mod) % mod;
                    }
//                  cout << i << " " << st << " " << en << " right " << dp[i][st][en][1] << endl;
//                  cout << i << " " << st << " " << en << " left " << dp[i][st][en][0] << endl;
                }
            }
        }
        memset (fen, 0, sizeof fen);
        for (int st = 1; st <= i; st ++) {
            for (int en = 1; en <= i; en ++) {
                change (st, dp[st][en][1], en, 1);
                change (st, dp[st][en][0], en, 0);
            }
        }
    }
    cout << (dp[s][t][1] + dp[s][t][0]) % mod << endl;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 102648 KB Output is correct
2 Correct 186 ms 102812 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 102648 KB Output is correct
2 Correct 186 ms 102812 KB Output is correct
3 Correct 675 ms 102988 KB Output is correct
4 Correct 1024 ms 103016 KB Output is correct
5 Correct 908 ms 103252 KB Output is correct
6 Correct 917 ms 103252 KB Output is correct
7 Correct 927 ms 103252 KB Output is correct
8 Correct 1000 ms 103252 KB Output is correct
9 Correct 933 ms 103256 KB Output is correct
10 Correct 886 ms 103328 KB Output is correct
11 Correct 896 ms 103328 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 102648 KB Output is correct
2 Correct 186 ms 102812 KB Output is correct
3 Correct 675 ms 102988 KB Output is correct
4 Correct 1024 ms 103016 KB Output is correct
5 Correct 908 ms 103252 KB Output is correct
6 Correct 917 ms 103252 KB Output is correct
7 Correct 927 ms 103252 KB Output is correct
8 Correct 1000 ms 103252 KB Output is correct
9 Correct 933 ms 103256 KB Output is correct
10 Correct 886 ms 103328 KB Output is correct
11 Correct 896 ms 103328 KB Output is correct
12 Execution timed out 2070 ms 103540 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 102648 KB Output is correct
2 Correct 186 ms 102812 KB Output is correct
3 Correct 675 ms 102988 KB Output is correct
4 Correct 1024 ms 103016 KB Output is correct
5 Correct 908 ms 103252 KB Output is correct
6 Correct 917 ms 103252 KB Output is correct
7 Correct 927 ms 103252 KB Output is correct
8 Correct 1000 ms 103252 KB Output is correct
9 Correct 933 ms 103256 KB Output is correct
10 Correct 886 ms 103328 KB Output is correct
11 Correct 896 ms 103328 KB Output is correct
12 Execution timed out 2070 ms 103540 KB Time limit exceeded
13 Halted 0 ms 0 KB -