Submission #873742


Source Code Expand

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

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back

using uint=unsigned int;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;

int read(){
	int i;
	scanf("%d",&i);
	return i;
}

struct State{
	int v;
	State* nx[26];
	State(){
		v=0;
		fill(nx,nx+26,(State*)(NULL));
	}
};
vector<State> buf;
int bufUsed;
State* newState(){
	return &buf[bufUsed++];
}
State* root;
void trieDfs(State* cur,const string& s,int i,int v){
	if(i==(int)s.size())
		cur->v=max(cur->v,v);
	else{
		if(!(cur->nx[(int)s[i]]))
			cur->nx[(int)s[i]]=newState();
		trieDfs(cur->nx[(int)s[i]],s,i+1,v);
	}
}
void Init(const vector<pair<string,int>>& strs){
	int sz=1;
	for(auto&& s:strs)
		sz+=s.first.size();
	buf.resize(sz);
	root=newState();
	for(auto&& s:strs)
		trieDfs(root,s.first,0,s.second);
}

string readString(){
	char strbuf[3341919];
	scanf("%s",strbuf);
	return string(strbuf);
}

int dp[3341919];

int main(){
	string s=readString();
	for(auto& c:s)c-='a';
	int n=s.size(),m=read();
	vector<pair<string,int>> dict(m);
	REP(i,m){
		dict[i].first=readString();
		for(auto& c:dict[i].first)c-='a';
	}
	REP(i,m)
		dict[i].second=read();
	Init(dict);
	REP(i,n){
		dp[i+1]=max(dp[i+1],dp[i]);
		State* cur=root;
		int p=0;
		while(i+p<n&&cur->nx[int(s[i+p])]){
			cur=cur->nx[int(s[i+p])];
			p++;
			dp[i+p]=max(dp[i+p],dp[i]+cur->v);
		}
	}
	cout<<dp[n]<<endl;
}

Submission Info

Submission Time
Task C - たんごたくさん
User maroonrk
Language C++14 (GCC 5.4.1)
Score 700
Code Size 1551 Byte
Status AC
Exec Time 669 ms
Memory 213632 KB

Compile Error

./Main.cpp: In function ‘int read()’:
./Main.cpp:16:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&i);
                ^
./Main.cpp: In function ‘std::string readString()’:
./Main.cpp:55:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",strbuf);
                    ^

Judge Result

Set Name All
Score / Max Score 700 / 700
Status
AC × 38
Set Name Test Cases
All 00_sample_01, 00_sample_02, 00_sample_03, 01_manual_02, 01_manual_03, 01_manual_04, 01_manual_05, 01_manual_06, 03_manual_01, 03_manual_02, 03_manual_03, 03_manual_04, 20_random_017, 20_random_057, 20_random_088, 20_random_small_01, 20_random_small_02, 20_random_small_03, 20_random_small_04, 20_random_small_05, 30_random_large_01, 30_random_large_02, 30_random_large_03, 30_random_large_04, 30_random_large_05, 40_random_001, 40_random_002, 40_random_004, 40_random_008, 80_collision_01, 80_collision_02, 90_large_01, 97_maximum_01, 97_maximum_02, 98_maximum_01, 98_maximum_02, 99_maximum_01, 99_maximum_02
Case Name Status Exec Time Memory
00_sample_01 AC 4 ms 256 KB
00_sample_02 AC 4 ms 256 KB
00_sample_03 AC 4 ms 256 KB
01_manual_02 AC 9 ms 1408 KB
01_manual_03 AC 4 ms 256 KB
01_manual_04 AC 4 ms 256 KB
01_manual_05 AC 4 ms 256 KB
01_manual_06 AC 4 ms 256 KB
03_manual_01 AC 631 ms 213632 KB
03_manual_02 AC 646 ms 213632 KB
03_manual_03 AC 669 ms 213632 KB
03_manual_04 AC 200 ms 5760 KB
20_random_017 AC 12 ms 3968 KB
20_random_057 AC 7 ms 1792 KB
20_random_088 AC 23 ms 9088 KB
20_random_small_01 AC 4 ms 256 KB
20_random_small_02 AC 4 ms 256 KB
20_random_small_03 AC 4 ms 256 KB
20_random_small_04 AC 4 ms 256 KB
20_random_small_05 AC 4 ms 256 KB
30_random_large_01 AC 146 ms 69504 KB
30_random_large_02 AC 130 ms 62208 KB
30_random_large_03 AC 230 ms 107008 KB
30_random_large_04 AC 213 ms 94208 KB
30_random_large_05 AC 213 ms 98944 KB
40_random_001 AC 135 ms 55680 KB
40_random_002 AC 24 ms 10496 KB
40_random_004 AC 26 ms 7168 KB
40_random_008 AC 119 ms 52992 KB
80_collision_01 AC 541 ms 213632 KB
80_collision_02 AC 542 ms 213632 KB
90_large_01 AC 237 ms 14208 KB
97_maximum_01 AC 135 ms 55808 KB
97_maximum_02 AC 125 ms 55680 KB
98_maximum_01 AC 11 ms 1408 KB
98_maximum_02 AC 10 ms 1408 KB
99_maximum_01 AC 539 ms 213632 KB
99_maximum_02 AC 497 ms 213632 KB