oj.uz

Submission #1019290

# Submission time Handle Problem Language Result Execution time Memory
1019290 2024-07-10T17:05:33 Z andrei_iorgulescu Boat (APIO16_boat) C++14
36 / 100
 2000 ms 8452 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

int modulo = 1e9 + 7;

int n;
int l[505],r[505];
int dpcur[1005][505], dpant[1005][505];
int fact[1005],invfact[1005];

int lgpow(int x,int y)
{
    int z = 1;
    while (y != 0)
    {
        if (y % 2 == 1)
            z = z * x % modulo;
        x = x * x % modulo;
        y /= 2;
    }
    return z;
}

int ways(int x, int y)
{
    int rr = 1;
    for (int i = x - y + 1; i <= x; i++)
        rr = rr * i % modulo;
    rr *= invfact[y];
    rr %= modulo;
    return rr;
}

signed main()
{
    fact[0] = invfact[0] = 1;
    for (int i = 1; i <= 1000; i++)
        fact[i] = i * fact[i - 1] % modulo, invfact[i] = lgpow(fact[i],modulo - 2);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> l[i] >> r[i];
    set<int> timpi;
    for (int i = 1; i <= n; i++)
        timpi.insert(l[i]),timpi.insert(r[i] + 1);
    vector<int> t;
    for (auto it : timpi)
        t.push_back(it);
    vector<pair<int,int>> intv;
    for (int i = 0; i < t.size() - 1; i++)
        intv.push_back({t[i],t[i + 1] - 1});
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < intv.size(); j++)
        {
            for (int q = 1; q <= i; q++)
            {
                dpcur[j][q] = dpant[j][q];
                if (r[i] < intv[j].first or l[i] > intv[j].first)
                    continue;
                if (q != 1)
                {
                    int adg = dpant[j][q - 1] * ways(intv[j].second - intv[j].first + 1,q) % modulo * lgpow(ways(intv[j].second - intv[j].first + 1,q - 1),modulo - 2) % modulo;
                    dpcur[j][q] += adg;
                    dpcur[j][q] %= modulo;
                }
                else
                {
                    int cf = intv[j].second - intv[j].first + 1;
                    int sm = 1;///nu mai e nimic inainte
                    for (int jp = 0; jp < j; jp++)
                        for (int qp = 0; qp < i; qp++)
                            sm += dpant[jp][qp];
                    sm %= modulo;
                    sm *= cf;
                    sm %= modulo;
                    dpcur[j][q] += sm;
                    dpcur[j][q] %= modulo;
                }
            }
        }
        for (int j = 0; j < intv.size(); j++)
        {
            for (int q = 1; q <= i; q++)
                dpant[j][q] = dpcur[j][q];
        }
    }
    int ans = 0;
    for (int j = 0; j < intv.size(); j++)
    {
        for (int q = 1; q <= n; q++)
            ans += dpant[j][q];
    }
    ans %= modulo;
    cout << ans;
    return 0;
}

/**
Exista O(N) intervale relevante de nr barci
dp[i][j][q] = in cate moduri pot lua primii i jucatori, astfel incat ultimul luat sa trimita barci in intervalul j, de fapt q trimitand asa
dp[i][j][q] vine din:
- dp[i - 1][j][q] (omul i sta pe bara), coef = 1
- daca q != 1, dp[i - 1][j][q - 1], coef = ways(q, len[j]) / ways(q - 1, len[j]) unde consider 0 / 0 = 0
- daca q = 1, dp[i - 1][j'][q'], coef = len[j]

Deci pentru majoritatea starilor (tehnic N^3) am o singura tranzitie, pentru N^2 insa am N^2 tranzitii si dau in N^4
Dar tranzitia aia e coef * suma(dp[i - 1][j'][q']) cu j' < j si orice q' (pot chiar sa parcurg j' ca sa nu imi tin sume dubioase ca e N^3)

ways(x, len) = C(len,x)
**/

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:52:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for (int i = 0; i < t.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~
boat.cpp:56:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j = 0; j < intv.size(); j++)
      |                         ~~^~~~~~~~~~~~~
boat.cpp:84:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int j = 0; j < intv.size(); j++)
      |                         ~~^~~~~~~~~~~~~
boat.cpp:91:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for (int j = 0; j < intv.size(); j++)
      |                     ~~^~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 8280 KB Output is correct
2 Correct 410 ms 8440 KB Output is correct
3 Correct 449 ms 8436 KB Output is correct
4 Correct 400 ms 8280 KB Output is correct
5 Correct 464 ms 8400 KB Output is correct
6 Correct 421 ms 8284 KB Output is correct
7 Correct 423 ms 8280 KB Output is correct
8 Correct 413 ms 8280 KB Output is correct
9 Correct 422 ms 8280 KB Output is correct
10 Correct 454 ms 8444 KB Output is correct
11 Correct 423 ms 8440 KB Output is correct
12 Correct 445 ms 8284 KB Output is correct
13 Correct 439 ms 8284 KB Output is correct
14 Correct 440 ms 8452 KB Output is correct
15 Correct 451 ms 8444 KB Output is correct
16 Correct 237 ms 1884 KB Output is correct
17 Correct 227 ms 1880 KB Output is correct
18 Correct 242 ms 1760 KB Output is correct
19 Correct 230 ms 2000 KB Output is correct
20 Correct 237 ms 1884 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 8280 KB Output is correct
2 Correct 410 ms 8440 KB Output is correct
3 Correct 449 ms 8436 KB Output is correct
4 Correct 400 ms 8280 KB Output is correct
5 Correct 464 ms 8400 KB Output is correct
6 Correct 421 ms 8284 KB Output is correct
7 Correct 423 ms 8280 KB Output is correct
8 Correct 413 ms 8280 KB Output is correct
9 Correct 422 ms 8280 KB Output is correct
10 Correct 454 ms 8444 KB Output is correct
11 Correct 423 ms 8440 KB Output is correct
12 Correct 445 ms 8284 KB Output is correct
13 Correct 439 ms 8284 KB Output is correct
14 Correct 440 ms 8452 KB Output is correct
15 Correct 451 ms 8444 KB Output is correct
16 Correct 237 ms 1884 KB Output is correct
17 Correct 227 ms 1880 KB Output is correct
18 Correct 242 ms 1760 KB Output is correct
19 Correct 230 ms 2000 KB Output is correct
20 Correct 237 ms 1884 KB Output is correct
21 Execution timed out 2068 ms 7732 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 2132 KB Output is correct
2 Correct 143 ms 1884 KB Output is correct
3 Correct 137 ms 1884 KB Output is correct
4 Correct 163 ms 2048 KB Output is correct
5 Correct 171 ms 1880 KB Output is correct
6 Correct 250 ms 1884 KB Output is correct
7 Correct 246 ms 2044 KB Output is correct
8 Correct 227 ms 2060 KB Output is correct
9 Correct 227 ms 1880 KB Output is correct
10 Correct 232 ms 2044 KB Output is correct
11 Correct 132 ms 1884 KB Output is correct
12 Correct 105 ms 1880 KB Output is correct
13 Correct 107 ms 2044 KB Output is correct
14 Correct 120 ms 1884 KB Output is correct
15 Correct 138 ms 1884 KB Output is correct
16 Correct 88 ms 1372 KB Output is correct
17 Correct 75 ms 1116 KB Output is correct
18 Correct 107 ms 1284 KB Output is correct
19 Correct 80 ms 1368 KB Output is correct
20 Correct 102 ms 1116 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 8280 KB Output is correct
2 Correct 410 ms 8440 KB Output is correct
3 Correct 449 ms 8436 KB Output is correct
4 Correct 400 ms 8280 KB Output is correct
5 Correct 464 ms 8400 KB Output is correct
6 Correct 421 ms 8284 KB Output is correct
7 Correct 423 ms 8280 KB Output is correct
8 Correct 413 ms 8280 KB Output is correct
9 Correct 422 ms 8280 KB Output is correct
10 Correct 454 ms 8444 KB Output is correct
11 Correct 423 ms 8440 KB Output is correct
12 Correct 445 ms 8284 KB Output is correct
13 Correct 439 ms 8284 KB Output is correct
14 Correct 440 ms 8452 KB Output is correct
15 Correct 451 ms 8444 KB Output is correct
16 Correct 237 ms 1884 KB Output is correct
17 Correct 227 ms 1880 KB Output is correct
18 Correct 242 ms 1760 KB Output is correct
19 Correct 230 ms 2000 KB Output is correct
20 Correct 237 ms 1884 KB Output is correct
21 Execution timed out 2068 ms 7732 KB Time limit exceeded
22 Halted 0 ms 0 KB -