제출 #638649

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638649		PoonYaPat	Boat (APIO16_boat)	C++14	36 / 100	2071 ms	4292 KiB

boat

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 9
• Subtask 2: 0 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42