Submission #710944

#	Time	Username	Problem	Language	Result	Execution time	Memory
710944		gustjwkd1007	Boat (APIO16_boat)	C++17	0 / 100	3 ms	468 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(x, y) uniform_int_distribution<int>(x, y)(rng)

ll mod(ll a, ll b=(ll)P) { return ((a%b) + b) % b; }
ll ext_gcd(ll a, ll b, ll &x, ll &y) {
    ll g = a; x = 1, y = 0;
    if(b) g = ext_gcd(b, a % b, y, x), y -= a / b * x;
    return g;
}
ll inv(ll a, ll m=(ll)P) {
    ll x, y; ll g = ext_gcd(a, m, x, y);
    if(g > 1) return -1;
    return mod(x, m);
}
int N;
int input[2][1000];
vector <ll> dp[2][2000];
set <int> ms;
vector <pii> A;
vector <int> len;
int main() {
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr);
    cin >> N;
    for(int i=1;i<=N;i++)
        cin >> input[0][i] >> input[1][i];
    ms.insert(0);
    for(int i=1;i<=N;i++)
        ms.insert(input[0][i]), ms.insert(input[1][i]);
    auto it = ms.begin();
    while(it!=ms.end()) {
        int now = *it;
        it++;
        A.push_back({now, now});
        if(it!=ms.end() && now+1 <= *it-1)
            A.push_back({now+1, *it-1});
    }
    for(pii x : A)
        len.push_back(x.se-x.fi+1);

    for(int i=0;i<A.size();i++)
        dp[0][i].push_back(1);

    for(int i=1;i<=N;i++){
        dp[i&1][0].clear();
        dp[i&1][0].push_back(dp[(i-1)&1][0][0]);
        for(int j=1;j<A.size();j++){
            dp[i&1][j].clear();
            dp[i&1][j].push_back(dp[i&1][j-1][0]+dp[(i-1)&1][j][0]-dp[(i-1)&1][j-1][0]);
            if(A[j].fi > input[1][i] || input[0][i] > A[j].se)
                continue;
            dp[i&1][j].push_back(dp[(i-1)&1][j-1][0]);
            for(int k=2;k<min((int)dp[(i-1)&1][j].size()+1, len[j]+1);k++)
                dp[i&1][j].push_back(mod(mod((len[j]-k+1)*inv(k))*dp[(i-1)&1][j][k-1]));
            for(int k=1;k<dp[i&1][j].size();k++)
                dp[i&1][j][0] = mod(dp[i&1][j][0] + dp[i&1][j][k]);
        }
        /*
        for(int j=0;j<A.size();j++)
            cout << dp[i&1][j];
        cout << endl;
        */
    }

    cout << dp[N&1][A.size()-1][0]-1;
    
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0;i<A.size();i++)
      |                 ~^~~~~~~~~
boat.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j=1;j<A.size();j++){
      |                     ~^~~~~~~~~
boat.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for(int k=1;k<dp[i&1][j].size();k++)
      |                         ~^~~~~~~~~~~~~~~~~~

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