oj.uz

Submission #81748

# Submission time Handle Problem Language Result Execution time Memory
81748 2018-10-26T12:15:14 Z Saboon Kangaroo (CEOI16_kangaroo) C++14
36 / 100
 2000 ms 103392 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;

int 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 167 ms 102648 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 167 ms 102648 KB Output is correct
3 Correct 531 ms 102880 KB Output is correct
4 Correct 839 ms 103140 KB Output is correct
5 Correct 793 ms 103140 KB Output is correct
6 Correct 860 ms 103248 KB Output is correct
7 Correct 871 ms 103256 KB Output is correct
8 Correct 905 ms 103256 KB Output is correct
9 Correct 998 ms 103256 KB Output is correct
10 Correct 935 ms 103256 KB Output is correct
11 Correct 930 ms 103256 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 167 ms 102648 KB Output is correct
3 Correct 531 ms 102880 KB Output is correct
4 Correct 839 ms 103140 KB Output is correct
5 Correct 793 ms 103140 KB Output is correct
6 Correct 860 ms 103248 KB Output is correct
7 Correct 871 ms 103256 KB Output is correct
8 Correct 905 ms 103256 KB Output is correct
9 Correct 998 ms 103256 KB Output is correct
10 Correct 935 ms 103256 KB Output is correct
11 Correct 930 ms 103256 KB Output is correct
12 Execution timed out 2061 ms 103392 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 167 ms 102648 KB Output is correct
3 Correct 531 ms 102880 KB Output is correct
4 Correct 839 ms 103140 KB Output is correct
5 Correct 793 ms 103140 KB Output is correct
6 Correct 860 ms 103248 KB Output is correct
7 Correct 871 ms 103256 KB Output is correct
8 Correct 905 ms 103256 KB Output is correct
9 Correct 998 ms 103256 KB Output is correct
10 Correct 935 ms 103256 KB Output is correct
11 Correct 930 ms 103256 KB Output is correct
12 Execution timed out 2061 ms 103392 KB Time limit exceeded
13 Halted 0 ms 0 KB -