結果

問題 No.695 square1001 and Permutation 4
ユーザー nikutto_nikutto_
提出日時 2018-06-09 20:55:51
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,861 bytes
コンパイル時間 2,610 ms
コンパイル使用メモリ 168,924 KB
実行使用メモリ 158,340 KB
最終ジャッジ日時 2024-07-22 19:31:55
合計ジャッジ時間 8,639 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 63 ms
5,376 KB
testcase_02 AC 37 ms
5,376 KB
testcase_03 AC 38 ms
5,376 KB
testcase_04 AC 265 ms
5,376 KB
testcase_05 AC 267 ms
17,408 KB
testcase_06 AC 457 ms
5,376 KB
testcase_07 AC 600 ms
5,376 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 101 ms
5,376 KB
testcase_11 MLE -
testcase_12 MLE -
testcase_13 MLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
const ll MOD=100000000000000007;


int main(){
    int n,m;
    cin>>n>>m;
    vector<int> x(m);
    for(int i=0;i<m;i++) cin>>x[i];
    sort(x.begin(),x.end());
    vector<int> belong(m);
    for(int i=0;i<m;i++) belong[i]=i;
    vector<deque<ll>> dp(m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m-1;j++){
            if(i+x[j]==x[j+1]){
                while(!dp[belong[j+1]].empty()){
                    dp[belong[j]].push_back(dp[belong[j+1]].front());
                    dp[belong[j+1]].pop_front();
                }                                
                belong[j+1]=belong[j];
            }
        }
        if(i<x[0]){
            ll step=(i==0);
            for(int j=0;j<m;j++){
                if(i+x[j]<n){
                    int to=i+x[j]-x[belong[j]];
                    if(dp[belong[j]].size()>to){
                        dp[belong[j]][to]+=step;
                        if(dp[belong[j]][to]>=MOD){
                            dp[belong[j]][to]-=MOD;
                        }
                    }
                    else dp[belong[j]].push_back(step);
                }
            }
        }
        else{
            ll step=dp[0].front();
            dp[0].pop_front();
            for(int j=0;j<m;j++){
                if(i+x[j]<n){                                        
                    int to=(belong[j]==0 ? x[j]-1 : i+x[j]-x[belong[j]]);
                    if(dp[belong[j]].size()>to){
                        dp[belong[j]][to]+=step;
                        if(dp[belong[j]][to]>=MOD){
                            dp[belong[j]][to]-=MOD;
                        }
                    }
                    else dp[belong[j]].push_back(step);
                }
            }
        }
        
    }
    cout<<dp[0].back();
    return 0;
}
0