oj.uz

답안 #81750

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
81750 2018-10-26T12:17:36 Z Saboon 캥거루 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -