提出 #816057


ソースコード 拡げる

Copy
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) do { \
    fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
    _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif

template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }

void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
    _R(head);
    R(tail...);
}

template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
    for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
        if ( i!=x.cbegin() ) putchar(' ');
        _W(*i);
    }
}

void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
    _W(head);
    putchar(sizeof...(tail)?' ':'\n');
    W(tail...);
}

#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
    freopen(name ".in","r",stdin); \
    freopen(name ".out","w",stdout); \
} while (0)
#endif

// }}}

const int M=2e5+10;
const LL MOD=1e9+7;


int n,x,y,z,tot,m;
VI vv[M];

int path[20];
void dfs( int lv, int s ) {
    vv[m++]=VI(path,path+lv);
    int u=min(tot-s,10);
    REP1(i,1,u) {
        path[lv]=i;
        dfs(lv+1,s+i);
    }
}

bool good[M];
VI to[M];
LL dp[2][M];

int main() {
    R(n,x,y,z);
    tot=x+y+z;
    dfs(0,0);
    sort(vv,vv+m);
    dump(m);
    REP(i,m) {
        int s=0,t=0;
        for ( int j:vv[i] ) {
            s+=j;
            if ( (t==0 && s==x) || (t==1 && s==y) || (t==2 && s==z) ) t++,s=0;
        }
        if ( t==3 ) good[i]=1;
    }
    REP(i,m) {
        REP1(j,1,10) {
            if ( good[i] ) to[i].PB(i);
            else if ( j>tot ) to[i].PB(0);
            else {
                VI v;
                v.PB(j);
                int s=j;
                for ( int k=SZ(vv[i])-1; k>=0; k-- ) {
                    s+=vv[i][k];
                    if ( s>tot ) break;
                    v.PB(vv[i][k]);
                }
                reverse(ALL(v));
                int idx=lower_bound(vv,vv+m,v)-vv;
                assert(vv[idx]==v);
                to[i].PB(idx);
            }
        }
    }
    int u=0;
    dp[u][0]=1;
    REP(i,n) {
        memset(dp[u^1],0,m*sizeof(LL));
        REP(j,m) {
            int me=dp[u][j]%MOD;
            for ( int k:to[j] ) dp[u^1][k]+=me;
        }
        u^=1;
    }
    LL ans=0;
    REP(i,m) if ( good[i] ) ans+=dp[u][i];
    ans%=MOD;
    W(ans);
    return 0;
}

提出情報

提出日時
問題 E - 和風いろはちゃん / Iroha and Haiku
ユーザ shik
言語 C++14 (GCC 5.4.1)
得点 700
コード長 4378 Byte
結果
実行時間 1274 ms
メモリ 28160 KB

コンパイルエラー

./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:46: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                              ^
./Main.cpp: In function ‘void _R(int&)’:
./Main.cpp:61:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( int &x ) { scanf("%d",&x); }
                                   ^
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                               ^
./Main.cpp: In function ‘void _R(double&)’:
./Main.cpp:63:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-resu...

テストケース

セット名 得点 / 配点 テストケース
Sample 0 / 0 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt
All 700 / 700 subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_max1.txt, subtask1_max2.txt, subtask1_max3.txt, subtask1_min1.txt, subtask1_min2.txt, subtask1_min3.txt
ケース名 結果 実行時間 メモリ
subtask0_sample_01.txt 1114 ms 28160 KB
subtask0_sample_02.txt 1105 ms 28160 KB
subtask0_sample_03.txt 23 ms 9728 KB
subtask0_sample_04.txt 1274 ms 28160 KB
subtask1_01.txt 21 ms 9600 KB
subtask1_02.txt 45 ms 10112 KB
subtask1_03.txt 31 ms 9856 KB
subtask1_04.txt 72 ms 10752 KB
subtask1_05.txt 22 ms 9728 KB
subtask1_06.txt 20 ms 9600 KB
subtask1_07.txt 25 ms 9728 KB
subtask1_08.txt 20 ms 9600 KB
subtask1_09.txt 21 ms 9600 KB
subtask1_10.txt 22 ms 9728 KB
subtask1_11.txt 21 ms 9600 KB
subtask1_12.txt 262 ms 14080 KB
subtask1_13.txt 72 ms 10752 KB
subtask1_14.txt 22 ms 9728 KB
subtask1_15.txt 77 ms 10752 KB
subtask1_16.txt 582 ms 18816 KB
subtask1_17.txt 139 ms 11904 KB
subtask1_18.txt 375 ms 14080 KB
subtask1_19.txt 142 ms 11904 KB
subtask1_20.txt 45 ms 10112 KB
subtask1_21.txt 293 ms 14080 KB
subtask1_22.txt 147 ms 11904 KB
subtask1_23.txt 140 ms 11904 KB
subtask1_24.txt 75 ms 10752 KB
subtask1_25.txt 141 ms 11904 KB
subtask1_max1.txt 1263 ms 28160 KB
subtask1_max2.txt 1266 ms 28160 KB
subtask1_max3.txt 601 ms 18816 KB
subtask1_min1.txt 20 ms 9600 KB
subtask1_min2.txt 20 ms 9600 KB
subtask1_min3.txt 1093 ms 28160 KB