oj.uz

Submission #47256

# Submission time Handle Problem Language Result Execution time Memory
47256 2018-04-29T18:31:41 Z ngkan146 Boat (APIO16_boat) C++11
0 / 100
 272 ms 2296 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = (ll) 1e9+7;
int n, a[505], b[505];
ll f[505][2005];
ll g[505];

int main(){
    iostream::sync_with_stdio(0);
    cin >> n;
    vector <int> lst;
    for(int i=1;i<=n;i++)
        cin >> a[i] >> b[i],
        lst.push_back(a[i]),
        lst.push_back(b[i]);
    sort(lst.begin(), lst.end());
    lst.resize(unique(lst.begin(),lst.end()) - lst.begin());
    vector <pair<int,int> > range;
    for(int i=0;i<lst.size();i++){
        range.push_back({lst[i], lst[i]});
        if (i != lst.size() - 1 && lst[i]+1 <= lst[i+1]-1)
            range.push_back({lst[i]+1, lst[i+1]-1});
    }
    range.insert(range.begin(), {-1,-1});
    g[0] = 1;
    ll ans = 0;
    for(int j = 1;j < range.size();j ++){
        // f[i][j] = cnt of way that end at i and value of i in range j
        int len = range[j].second - range[j].first + 1;
        ll arr[505];
        arr[0] = 1;

        for(int i=1;i<=n;i++)
            arr[i] = arr[i-1] * (len+1-i) % mod;

        for(int i=1;i<=n;i++){
            if (range[j].first < a[i] || b[i] < range[j].second)
                continue;
            int possiBoat = 0;

            for(int ii=i;ii>=1;ii--){
                if (!(a[ii] <= range[j].first && range[j].second <= b[ii]))  continue;
                possiBoat += (a[ii] <= range[j].first && range[j].second <= b[ii]);
                if (possiBoat > len)    break;
                for(int iii=ii-1;iii>=0;iii--){
                    for(int cnt=1;cnt<=possiBoat;cnt++){
                        f[i][j] = (f[i][j] + g[iii] * arr[cnt] % mod) % mod;
                    }
                }
            }
            ans += f[i][j];
        }
        for(int i=0;i<=n;i++){
            g[i] += f[i][j];
        }
    }
    cout << ans;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<lst.size();i++){
                 ~^~~~~~~~~~~
boat.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i != lst.size() - 1 && lst[i]+1 <= lst[i+1]-1)
             ~~^~~~~~~~~~~~~~~~~
boat.cpp:28:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 1;j < range.size();j ++){
                   ~~^~~~~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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