oj.uz

답안 #85841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
85841 2018-11-21T22:10:50 Z kraljlavova1 Mate (COCI18_mate) C++11
80 / 100
 2000 ms 102784 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long int llint;
const int MOD=1e9+7,MAXQ=500010,MAXS=2010;
string s,xy[MAXQ];
llint sol[MAXS][26][26];
int q,len,l[MAXQ];
map<string,vector<int> >mp;
map<pair<string,int>,int>bio;
llint povrh[MAXS][MAXS];
void pov(){
	povrh[0][0]=1;
	for(int i=1;i<MAXS;i++){
		for(int j=0;j<MAXS;j++){
			if(j==0){
				povrh[i][j]=1;
				continue;
			}
			povrh[i][j]=povrh[i-1][j]+povrh[i-1][j-1];
			povrh[i][j]%=MOD;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	pov();
	cin>>s;
	cin>>q;
	len=s.length();
	for(int i=0;i<q;i++){
		cin>>l[i]>>xy[i];
		if(!bio[{xy[i],l[i]}]){
			mp[xy[i]].push_back(l[i]);
			bio[{xy[i],l[i]}]=1;
		}
	}
	for(int i=0;i<len;i++){
		for(int j=i+1;j<len;j++){
			string a="";
			a+=s[i];
			a+=s[j];
			for(int k=0;k<mp[a].size();k++){
				int d=mp[a][k];
				sol[d][a[0]-'a'][a[1]-'a']+=povrh[i][d-2];
				sol[d][a[0]-'a'][a[1]-'a']%=MOD;
			}
		}
	}
	for(int i=0;i<q;i++){
		cout<<sol[l[i]][xy[i][0]-'a'][xy[i][1]-'a']<<"\n";
	}
	return 0;
}

Compilation message

mate.cpp: In function 'int main()':
mate.cpp:43:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<mp[a].size();k++){
                ~^~~~~~~~~~~~~

Subtask #1
80.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 49912 KB Output is correct
2 Correct 70 ms 49912 KB Output is correct
3 Correct 72 ms 49912 KB Output is correct
4 Correct 88 ms 50416 KB Output is correct
5 Correct 531 ms 58240 KB Output is correct
6 Correct 614 ms 58876 KB Output is correct
7 Correct 489 ms 58876 KB Output is correct
8 Correct 445 ms 58876 KB Output is correct
9 Execution timed out 2064 ms 102712 KB Time limit exceeded
10 Execution timed out 2077 ms 102784 KB Time limit exceeded