結果

問題 No.515 典型LCP
コンテスト
ユーザー ふっぴー
提出日時 2017-05-08 11:49:21
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
結果
MLE  
実行時間 -
コード長 1,403 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,940 ms
コンパイル使用メモリ 176,828 KB
実行使用メモリ 814,720 KB
最終ジャッジ日時 2024-09-14 17:13:26
合計ジャッジ時間 6,268 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other MLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define loop(i,a,b) for(i=a;i<b;i++)
#define rloop(i,a,b) for(i=a;i>=b;i--)
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
const int inf=1000000001;
const ll INF=1e16;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846

int main(){
  int n,i,j,k,l1,l2,x,d,m;
  cin>>n;
  vs s(n+1);
  loop(k,1,n+1){
    cin>>s[k];
  }
  vii dp(n+1,vi(n+1,-1));
  vii sumi(n+1,vi(n+1));
  cin>>m>>x>>d;
  ll sum=0;
  loop(k,1,m+1){
    int cnt=0;
    int t=0;
    bool flag=false;
    i=(x/(n-1))+1;
    j=(x%(n-1))+1;
    if(i>j){
      swap(i,j);
    }else{
      j++;
    }
    if(dp[i][j]==-1){
      loop(l1,0,sumi[i].size()){
	loop(l2,0,sumi[sumi[i][l1]].size()){
	  if(sumi[sumi[i][l1]][l2]==j){
	    if(dp[sumi[i][l1]][i]!=dp[sumi[i][l1]][j]){
	      cnt=min(dp[sumi[i][l1]][i],dp[sumi[i][l1]][j]);
	      flag=true;
	      break;
	    }else{
	      t=max(t,dp[sumi[i][l1]][i]);
	    }
	  }
	}
	if(flag==true){
	  break;
	}
      }
      if(flag==false){
	cnt=t;
	loop(l1,t,min(s[i].size(),s[j].size())){
	  if(s[i][l1]==s[j][l1]){
	    cnt++;
	  }else{
	    break;
	  }
	}
      }
    }
    sumi[i].push_back(j);
    sumi[j].push_back(i);
    dp[i][j]=cnt;
    x=(x+d)%(n*(n-1));
    sum+=dp[i][j];
  }
  cout<<sum<<endl;
}
0