oj.uz

Submission #638649

# Submission time Handle Problem Language Result Execution time Memory
638649 2022-09-06T15:39:19 Z PoonYaPat Boat (APIO16_boat) C++14
36 / 100
 2000 ms 4292 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mod=1e9+7;
int n,c[1001],st[501],ed[501],cnt;
ll dp[501][1001];
set<int> ss;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n;
    for (int i=1; i<=n; ++i) {
        cin>>st[i]>>ed[i]; --st[i];
        ss.insert(st[i]);
        ss.insert(ed[i]);
    }
    cnt=ss.size()-1;
    int idx=0;
    for (auto it=ss.begin(); it!=ss.end(); ++it) c[idx++]=*it;

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

    for (int i=1; i<=n; ++i) {
        dp[i][0]=1; //don't send any boat

        for (int j=1; j<=cnt; ++j) { //consider from the range from c[j-1]+1 to c[j]
            dp[i][j]=dp[i][j-1];

            int idx=0;
            vector<int> v;

            for (auto k=i; k>0; --k) {
                if (st[k]<c[j] && c[j]<=ed[k]) {

                    ++idx;
                    v.push_back(c[j]-c[j-1]+idx-1);


                    int m=idx;
                    for (int h=0; h<v.size(); ++h) {
                        if (m==1) break;
                        int gcd=__gcd(m,v[h]);
                        v[h]/=gcd;
                        m/=gcd;
                    }

                    ll comb=1;
                    for (auto s : v) comb=(comb*s)%mod;

                    dp[i][j]=(dp[i][j]+comb*(dp[k-1][j-1]))%mod;
                }
            }
        }
    }
    cout<<dp[n][cnt]-1;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:41:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |                     for (int h=0; h<v.size(); ++h) {
      |                                   ~^~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 4196 KB Output is correct
2 Correct 209 ms 4224 KB Output is correct
3 Correct 208 ms 4264 KB Output is correct
4 Correct 222 ms 4188 KB Output is correct
5 Correct 211 ms 4272 KB Output is correct
6 Correct 141 ms 4188 KB Output is correct
7 Correct 141 ms 4292 KB Output is correct
8 Correct 147 ms 4280 KB Output is correct
9 Correct 147 ms 4172 KB Output is correct
10 Correct 143 ms 4212 KB Output is correct
11 Correct 184 ms 4228 KB Output is correct
12 Correct 144 ms 4240 KB Output is correct
13 Correct 146 ms 4248 KB Output is correct
14 Correct 149 ms 4288 KB Output is correct
15 Correct 141 ms 4232 KB Output is correct
16 Correct 57 ms 3020 KB Output is correct
17 Correct 56 ms 3068 KB Output is correct
18 Correct 56 ms 2984 KB Output is correct
19 Correct 59 ms 3036 KB Output is correct
20 Correct 56 ms 2980 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 4196 KB Output is correct
2 Correct 209 ms 4224 KB Output is correct
3 Correct 208 ms 4264 KB Output is correct
4 Correct 222 ms 4188 KB Output is correct
5 Correct 211 ms 4272 KB Output is correct
6 Correct 141 ms 4188 KB Output is correct
7 Correct 141 ms 4292 KB Output is correct
8 Correct 147 ms 4280 KB Output is correct
9 Correct 147 ms 4172 KB Output is correct
10 Correct 143 ms 4212 KB Output is correct
11 Correct 184 ms 4228 KB Output is correct
12 Correct 144 ms 4240 KB Output is correct
13 Correct 146 ms 4248 KB Output is correct
14 Correct 149 ms 4288 KB Output is correct
15 Correct 141 ms 4232 KB Output is correct
16 Correct 57 ms 3020 KB Output is correct
17 Correct 56 ms 3068 KB Output is correct
18 Correct 56 ms 2984 KB Output is correct
19 Correct 59 ms 3036 KB Output is correct
20 Correct 56 ms 2980 KB Output is correct
21 Execution timed out 2071 ms 1916 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 856 KB Output is correct
2 Correct 115 ms 872 KB Output is correct
3 Correct 164 ms 852 KB Output is correct
4 Correct 158 ms 872 KB Output is correct
5 Correct 183 ms 848 KB Output is correct
6 Correct 473 ms 824 KB Output is correct
7 Correct 470 ms 980 KB Output is correct
8 Correct 467 ms 776 KB Output is correct
9 Correct 477 ms 976 KB Output is correct
10 Correct 473 ms 848 KB Output is correct
11 Correct 251 ms 832 KB Output is correct
12 Correct 176 ms 836 KB Output is correct
13 Correct 246 ms 892 KB Output is correct
14 Correct 220 ms 856 KB Output is correct
15 Correct 235 ms 844 KB Output is correct
16 Correct 111 ms 772 KB Output is correct
17 Correct 92 ms 892 KB Output is correct
18 Correct 89 ms 796 KB Output is correct
19 Correct 76 ms 700 KB Output is correct
20 Correct 105 ms 756 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 4196 KB Output is correct
2 Correct 209 ms 4224 KB Output is correct
3 Correct 208 ms 4264 KB Output is correct
4 Correct 222 ms 4188 KB Output is correct
5 Correct 211 ms 4272 KB Output is correct
6 Correct 141 ms 4188 KB Output is correct
7 Correct 141 ms 4292 KB Output is correct
8 Correct 147 ms 4280 KB Output is correct
9 Correct 147 ms 4172 KB Output is correct
10 Correct 143 ms 4212 KB Output is correct
11 Correct 184 ms 4228 KB Output is correct
12 Correct 144 ms 4240 KB Output is correct
13 Correct 146 ms 4248 KB Output is correct
14 Correct 149 ms 4288 KB Output is correct
15 Correct 141 ms 4232 KB Output is correct
16 Correct 57 ms 3020 KB Output is correct
17 Correct 56 ms 3068 KB Output is correct
18 Correct 56 ms 2984 KB Output is correct
19 Correct 59 ms 3036 KB Output is correct
20 Correct 56 ms 2980 KB Output is correct
21 Execution timed out 2071 ms 1916 KB Time limit exceeded
22 Halted 0 ms 0 KB -