Submission #1098874
Source Code Expand
#include <bits/stdc++.h> #include<iostream> #include<cstdio> #include<vector> #include<queue> #include<map> #include<cstring> #include<string> #include <math.h> #include<algorithm> // #include <boost/multiprecision/cpp_int.hpp> #include<functional> #define int long long #define inf 1000000007 #define pa pair<int,int> #define ll long long #define pal pair<double,int> #define ppa pair<int,pa> #define ssa pair<string,int> #define mp make_pair #define pb push_back #define EPS (1e-10) #define equals(a,b) (fabs((a)-(b))<EPS) using namespace std; //priority_queue<int, vector<int>, greater<int> > que; class Point{ public: double x,y; Point(double x=0,double y=0):x(x),y(y) {} Point operator + (Point p) {return Point(x+p.x,y+p.y);} Point operator - (Point p) {return Point(x-p.x,y-p.y);} Point operator * (double a) {return Point(x*a,y*a);} Point operator / (double a) {return Point(x/a,y/a);} double absv() {return sqrt(norm());} double norm() {return x*x+y*y;} bool operator < (const Point &p) const{ return x != p.x ? x<p.x: y<p.y; } bool operator == (const Point &p) const{ return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS; } }; typedef Point Vector; struct Segment{ Point p1,p2; }; double hen(Vector a){ if(fabs(a.x)<EPS && a.y>0) return acos(0); else if(fabs(a.x)<EPS && a.y<0) return 3*acos(0); else if(fabs(a.y)<EPS && a.x<0) return 2*acos(0); else if(fabs(a.y)<EPS && a.x>0) return 0.0; else if(a.y>0) return acos(a.x/a.absv()); else return 2*acos(0)+acos(-a.x/a.absv()); } string itos( int i ) { ostringstream s ; s << i ; return s.str() ; } int gcd(int v,int b){ if(v>b) return gcd(b,v); if(v==b) return b; if(b%v==0) return v; return gcd(v,b%v); } double dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y; } double cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x; } double distans(double x1,double y1,double x2,double y2){ double rr=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2); return sqrt(rr); } int a[100020],b[100020]; //----------------kokomade tenpure------------ string s,t[110]; void no(){ cout<<"NO"<<endl; return; } signed main(){ int n,l[110]; cin>>n; cin>>s; s= "?"+s; for(int i=1;i<=n;i++){ cin>>t[i]; l[i]=t[i].length(); } int dp[1010]={0}; dp[0]=1; for(int i=0;i<s.length();i++){ if(dp[i]==0) continue; for(int j=1;j<=n;j++){ if(s.substr(i+1,l[j])==t[j]){ // cout<<"s"<<endl; dp[i+l[j]] += dp[i]; // cout<<dp[i+l[j]]<<endl; dp[i+l[j]] %=inf; } } } cout<<dp[s.length()-1]<<endl; // printf("%.10f\n",ans[n-1]); return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - エターナルスタティックファイナル |
User | smiken |
Language | C++ (G++ 4.6.4) |
Score | 60 |
Code Size | 4759 Byte |
Status | AC |
Exec Time | 28 ms |
Memory | 996 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 60 / 60 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample00.txt, 00_sample01.txt, 00_sample02.txt, 00_sample03.txt, 00_sample04.txt, 01_random00.txt, 01_random01.txt, 01_random02.txt, 01_random03.txt, 01_random04.txt, 01_random05.txt, 01_random06.txt, 01_random07.txt, 01_random08.txt, 01_random09.txt, 01_random10.txt, 01_random11.txt, 01_random12.txt, 01_random13.txt, 01_random14.txt, 01_random15.txt, 01_random16.txt, 01_random17.txt, 01_random18.txt, 01_random19.txt, 01_random20.txt, 01_random21.txt, 01_random22.txt, 01_random23.txt, 01_random24.txt, 01_random25.txt, 01_random26.txt, 01_random27.txt, 01_random28.txt, 01_random29.txt, 01_random30.txt, 01_random31.txt, 01_random32.txt, 01_random33.txt, 01_random34.txt, 01_random35.txt, 01_random36.txt, 01_random37.txt, 01_random38.txt, 01_random39.txt, 01_random40.txt, 01_random41.txt, 01_random42.txt, 01_random43.txt, 01_random44.txt, 01_random45.txt, 01_random46.txt, 01_random47.txt, 01_random48.txt, 01_random49.txt, 01_random50.txt, 01_random51.txt, 01_random52.txt, 01_random53.txt, 01_random54.txt, 01_random55.txt, 01_random56.txt, 01_random57.txt, 01_random58.txt, 01_random59.txt, 01_random61.txt, 01_random62.txt, 01_random63.txt, 01_random64.txt, 01_random65.txt, 01_random66.txt, 01_random67.txt, 01_random68.txt, 01_random69.txt, 01_random70.txt, 01_random71.txt, 01_random72.txt, 01_random73.txt, 01_random74.txt, 01_random75.txt, 01_random76.txt, 01_random77.txt, 01_random78.txt, 01_random79.txt, 01_random80.txt, 01_random81.txt, 01_random82.txt, 01_random83.txt, 01_random84.txt, 01_random85.txt, 01_random86.txt, 01_random87.txt, 01_random88.txt, 01_random89.txt, 01_random90.txt, 01_random91.txt, 01_random92.txt, 01_random93.txt, 01_random94.txt, 01_random95.txt, 01_random96.txt, 01_random97.txt, 01_random98.txt, 01_random99.txt, 02_manual00.txt, 02_manual01.txt, 02_manual02.txt, 02_manual03.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample00.txt | AC | 17 ms | 920 KB |
00_sample01.txt | AC | 17 ms | 924 KB |
00_sample02.txt | AC | 19 ms | 920 KB |
00_sample03.txt | AC | 18 ms | 916 KB |
00_sample04.txt | AC | 19 ms | 916 KB |
01_random00.txt | AC | 19 ms | 920 KB |
01_random01.txt | AC | 17 ms | 920 KB |
01_random02.txt | AC | 19 ms | 920 KB |
01_random03.txt | AC | 19 ms | 924 KB |
01_random04.txt | AC | 17 ms | 924 KB |
01_random05.txt | AC | 20 ms | 920 KB |
01_random06.txt | AC | 20 ms | 924 KB |
01_random07.txt | AC | 19 ms | 920 KB |
01_random08.txt | AC | 19 ms | 920 KB |
01_random09.txt | AC | 19 ms | 920 KB |
01_random10.txt | AC | 19 ms | 920 KB |
01_random11.txt | AC | 21 ms | 872 KB |
01_random12.txt | AC | 21 ms | 868 KB |
01_random13.txt | AC | 19 ms | 924 KB |
01_random14.txt | AC | 19 ms | 924 KB |
01_random15.txt | AC | 17 ms | 996 KB |
01_random16.txt | AC | 17 ms | 920 KB |
01_random17.txt | AC | 19 ms | 924 KB |
01_random18.txt | AC | 18 ms | 964 KB |
01_random19.txt | AC | 20 ms | 920 KB |
01_random20.txt | AC | 20 ms | 920 KB |
01_random21.txt | AC | 20 ms | 924 KB |
01_random22.txt | AC | 19 ms | 916 KB |
01_random23.txt | AC | 19 ms | 920 KB |
01_random24.txt | AC | 19 ms | 996 KB |
01_random25.txt | AC | 18 ms | 916 KB |
01_random26.txt | AC | 19 ms | 796 KB |
01_random27.txt | AC | 20 ms | 924 KB |
01_random28.txt | AC | 18 ms | 924 KB |
01_random29.txt | AC | 19 ms | 924 KB |
01_random30.txt | AC | 20 ms | 924 KB |
01_random31.txt | AC | 20 ms | 856 KB |
01_random32.txt | AC | 19 ms | 920 KB |
01_random33.txt | AC | 19 ms | 920 KB |
01_random34.txt | AC | 21 ms | 864 KB |
01_random35.txt | AC | 19 ms | 924 KB |
01_random36.txt | AC | 19 ms | 920 KB |
01_random37.txt | AC | 19 ms | 916 KB |
01_random38.txt | AC | 18 ms | 920 KB |
01_random39.txt | AC | 21 ms | 864 KB |
01_random40.txt | AC | 19 ms | 920 KB |
01_random41.txt | AC | 17 ms | 916 KB |
01_random42.txt | AC | 18 ms | 916 KB |
01_random43.txt | AC | 19 ms | 912 KB |
01_random44.txt | AC | 19 ms | 924 KB |
01_random45.txt | AC | 17 ms | 924 KB |
01_random46.txt | AC | 19 ms | 924 KB |
01_random47.txt | AC | 19 ms | 920 KB |
01_random48.txt | AC | 18 ms | 916 KB |
01_random49.txt | AC | 18 ms | 924 KB |
01_random50.txt | AC | 19 ms | 924 KB |
01_random51.txt | AC | 19 ms | 924 KB |
01_random52.txt | AC | 19 ms | 924 KB |
01_random53.txt | AC | 19 ms | 920 KB |
01_random54.txt | AC | 20 ms | 924 KB |
01_random55.txt | AC | 18 ms | 920 KB |
01_random56.txt | AC | 19 ms | 924 KB |
01_random57.txt | AC | 19 ms | 924 KB |
01_random58.txt | AC | 18 ms | 924 KB |
01_random59.txt | AC | 19 ms | 916 KB |
01_random61.txt | AC | 24 ms | 916 KB |
01_random62.txt | AC | 19 ms | 916 KB |
01_random63.txt | AC | 27 ms | 916 KB |
01_random64.txt | AC | 19 ms | 920 KB |
01_random65.txt | AC | 19 ms | 920 KB |
01_random66.txt | AC | 21 ms | 860 KB |
01_random67.txt | AC | 20 ms | 924 KB |
01_random68.txt | AC | 20 ms | 920 KB |
01_random69.txt | AC | 20 ms | 924 KB |
01_random70.txt | AC | 18 ms | 920 KB |
01_random71.txt | AC | 19 ms | 924 KB |
01_random72.txt | AC | 26 ms | 924 KB |
01_random73.txt | AC | 25 ms | 920 KB |
01_random74.txt | AC | 23 ms | 920 KB |
01_random75.txt | AC | 19 ms | 928 KB |
01_random76.txt | AC | 21 ms | 920 KB |
01_random77.txt | AC | 21 ms | 860 KB |
01_random78.txt | AC | 20 ms | 916 KB |
01_random79.txt | AC | 22 ms | 924 KB |
01_random80.txt | AC | 20 ms | 924 KB |
01_random81.txt | AC | 20 ms | 920 KB |
01_random82.txt | AC | 20 ms | 920 KB |
01_random83.txt | AC | 19 ms | 920 KB |
01_random84.txt | AC | 17 ms | 916 KB |
01_random85.txt | AC | 19 ms | 796 KB |
01_random86.txt | AC | 24 ms | 924 KB |
01_random87.txt | AC | 20 ms | 924 KB |
01_random88.txt | AC | 21 ms | 924 KB |
01_random89.txt | AC | 21 ms | 924 KB |
01_random90.txt | AC | 19 ms | 924 KB |
01_random91.txt | AC | 21 ms | 924 KB |
01_random92.txt | AC | 19 ms | 920 KB |
01_random93.txt | AC | 18 ms | 920 KB |
01_random94.txt | AC | 19 ms | 916 KB |
01_random95.txt | AC | 19 ms | 924 KB |
01_random96.txt | AC | 18 ms | 920 KB |
01_random97.txt | AC | 20 ms | 924 KB |
01_random98.txt | AC | 19 ms | 920 KB |
01_random99.txt | AC | 20 ms | 996 KB |
02_manual00.txt | AC | 28 ms | 920 KB |
02_manual01.txt | AC | 19 ms | 924 KB |
02_manual02.txt | AC | 17 ms | 924 KB |
02_manual03.txt | AC | 17 ms | 920 KB |