oj.uz

Submission #81750

# Submission time Handle Problem Language Result Execution time Memory
81750 2018-10-26T12:17:36 Z Saboon Kangaroo (CEOI16_kangaroo) C++14
36 / 100
 2000 ms 103420 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][3][maxn + 100];

ll get (int idx, int w, int d) {
    if (idx < 0)
        return 0;
    ll ret = 0;
    for (; idx; idx -= idx & -idx)
        ret = (ret + fen[w][d][idx]) % 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[w][d][idx] = (fen[w][d][idx] + 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 104 ms 102632 KB Output is correct
2 Correct 172 ms 102780 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 102632 KB Output is correct
2 Correct 172 ms 102780 KB Output is correct
3 Correct 539 ms 102964 KB Output is correct
4 Correct 820 ms 103096 KB Output is correct
5 Correct 797 ms 103096 KB Output is correct
6 Correct 812 ms 103096 KB Output is correct
7 Correct 757 ms 103200 KB Output is correct
8 Correct 791 ms 103200 KB Output is correct
9 Correct 814 ms 103200 KB Output is correct
10 Correct 816 ms 103200 KB Output is correct
11 Correct 789 ms 103200 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 102632 KB Output is correct
2 Correct 172 ms 102780 KB Output is correct
3 Correct 539 ms 102964 KB Output is correct
4 Correct 820 ms 103096 KB Output is correct
5 Correct 797 ms 103096 KB Output is correct
6 Correct 812 ms 103096 KB Output is correct
7 Correct 757 ms 103200 KB Output is correct
8 Correct 791 ms 103200 KB Output is correct
9 Correct 814 ms 103200 KB Output is correct
10 Correct 816 ms 103200 KB Output is correct
11 Correct 789 ms 103200 KB Output is correct
12 Execution timed out 2055 ms 103420 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 102632 KB Output is correct
2 Correct 172 ms 102780 KB Output is correct
3 Correct 539 ms 102964 KB Output is correct
4 Correct 820 ms 103096 KB Output is correct
5 Correct 797 ms 103096 KB Output is correct
6 Correct 812 ms 103096 KB Output is correct
7 Correct 757 ms 103200 KB Output is correct
8 Correct 791 ms 103200 KB Output is correct
9 Correct 814 ms 103200 KB Output is correct
10 Correct 816 ms 103200 KB Output is correct
11 Correct 789 ms 103200 KB Output is correct
12 Execution timed out 2055 ms 103420 KB Time limit exceeded
13 Halted 0 ms 0 KB -