oj.uz

Submission #199230

# Submission time Handle Problem Language Result Execution time Memory
199230 2020-01-30T15:00:08 Z anachor Boat (APIO16_boat) C++14
0 / 100
 23 ms 14072 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 1005, M = 998244353;
int l[N], r[N];
int st[N], len[N];

typedef long long LL;
LL dp[N][N];
LL sum[N][N];

LL power(LL a, LL p) {
    if (p==0)   return 1;
    LL ans = power(a, p/2);
    ans = (ans * ans)%M;
    if (p%2)    ans = (ans * a)%M;
    return ans;
}

LL f[N][N];
LL inv[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;
    map<int, int> mp;

    for (int i=1; i<=n; i++) {
        cin>>l[i]>>r[i];
        mp[l[i]] = mp[r[i]+1] = 0;
    }

    int sz = 0;
    for (auto &pr: mp) {
        pr.second = ++sz;
        st[sz] = pr.first;
    }

    for (int i=1; i<=n; i++)    inv[i] = power(i, M-2);
    for (int i=1; i<sz; i++)    {
        len[i] = st[i+1] - st[i];
        f[i][0] = 1;
        for (int j=1; j<=n; j++) {
            f[i][j] = (f[i][j-1]*(len[i]+j-1))%M;
            f[i][j] = (f[i][j]*inv[j])%M;
        }
    }

    dp[0][0] = 1;
    for (int i=0; i<=sz; i++)   sum[0][i] = 1;

    long long ans = 0;

    for (int i=1; i<=n; i++) {
        int ll = mp[l[i]], rr = mp[r[i]+1];

        for (int k=1; k<=sz; k++)  {
            if (!(l[i] <= st[k] && st[k] <= r[i]))  continue;
            int pos = 0;
            for (int j=i; j>=1; j--) {
                if (l[j] <= st[k] && st[k] <= r[j]) pos++;
                dp[i][k] = (dp[i][k] + f[k][pos] * sum[j-1][k-1])%M;
            }
        }

        for (int k=1; k<=sz; k++)
            sum[i][k] = (sum[i][k-1] + dp[i][k])%M;
        ans = (ans + sum[i][sz])%M;
    }

    cout<<ans<<endl;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:58:13: warning: unused variable 'll' [-Wunused-variable]
         int ll = mp[l[i]], rr = mp[r[i]+1];
             ^~
boat.cpp:58:28: warning: unused variable 'rr' [-Wunused-variable]
         int ll = mp[l[i]], rr = mp[r[i]+1];
                            ^~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 14072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 14072 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 14072 KB Output isn't correct
2 Halted 0 ms 0 KB -