Submission #1019303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019303		andrei_iorgulescu	Boat (APIO16_boat)	C++14	100 / 100	1354 ms	16588 KiB

boat

#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],smant[1005];
int fact[1005],invfact[1005];
int f[1005][505],invf[1005][505];

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)
{
    if (x < y)
        return 0;
    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 j = 0; j < intv.size(); j++)
    {
        for (int q = 1; q <= n; q++)
        {
            f[j][q] = ways(intv[j].second - intv[j].first + 1,q);
            invf[j][q] = lgpow(f[j][q],modulo - 2);
        }
    }
    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] * f[j][q] % modulo * invf[j][q - 1] % 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++)
                        sm += smant[jp];
                    sm %= modulo;
                    sm *= cf;
                    sm %= modulo;
                    dpcur[j][q] += sm;
                    dpcur[j][q] %= modulo;
                }
            }
        }
        for (int j = 0; j < intv.size(); j++)
        {
            smant[j] = 0;
            for (int q = 1; q <= i; q++)
                dpant[j][q] = dpcur[j][q],smant[j] += 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 (stderr)

boat.cpp: In function 'int main()':
boat.cpp:55: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]
   55 |     for (int i = 0; i < t.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~
boat.cpp:57: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]
   57 |     for (int j = 0; j < intv.size(); j++)
      |                     ~~^~~~~~~~~~~~~
boat.cpp:67: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]
   67 |         for (int j = 0; j < intv.size(); j++)
      |                         ~~^~~~~~~~~~~~~
boat.cpp:94: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]
   94 |         for (int j = 0; j < intv.size(); j++)
      |                         ~~^~~~~~~~~~~~~
boat.cpp:102: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]
  102 |     for (int j = 0; j < intv.size(); j++)
      |                     ~~^~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42