제출 #547032

#제출 시각아이디문제언어결과실행 시간메모리
547032ngraceCopy and Paste 3 (JOI22_copypaste3)C++14
62 / 100
3143 ms2097152 KiB
#include <vector> #include <iostream> #include <utility> #include <algorithm> #include <map> #include <set> #include <string> using namespace std; #define v vector #define ll long long #define pii pair<int,int> #define fi first #define se second int main(){ int N; cin>>N; string S; cin>>S; ll A,B,C; cin>>A>>B>>C; bool subtwo=true; for(char c:S){ if(c!=S[0]) subtwo=false; } if(subtwo){ ll out=A*N; v<ll> dp(N+1,N*A); dp[1]=A; for(int s=2; s<=N; s++){ dp[s] = min(s*A, dp[s-1]+A); for(int i=1; i<s; i++){ dp[s] = min(dp[s], dp[i] + B + C*(s/i) + (s%i)*A); } } cout<<dp[N]<<endl; return 0; } map<string, int> subToInd; v<v<int>> pairToInd(N, v<int>(N+1, 0)); v<set<int>> indToStarts(N*N+100); int subInd=1; for(int l=0; l<N; l++){ string sub=""; for(int r=l; r<N; r++){ sub.push_back(S[r]); int ind=subToInd[sub]; if(ind==0){ ind=subInd; subToInd[sub]=subInd++; } pairToInd[l][r-l+1] = ind; indToStarts[ind].insert(l); } } v<v<int>> nextOccur(N,v<int>(N+1,N)); for(int i=N-1; i>=0; i--){ for(int s=1; s<=N-i; s++){ int ind=pairToInd[i][s]; auto next = indToStarts[ind].lower_bound(i+s); if(next!=indToStarts[ind].end()) nextOccur[i][s]=(*next); } } v<v<ll>> dp(N, v<ll>(N,1e17)); for(int s=1; s<=N; s++){ for(int l=N-1; l>=0; l--){ dp[l][l]=A; if(s!=1 && l+s-1<N){ dp[l][l+s-1] = min(dp[l][l+s-1], A+dp[l+1][l+s-1]); dp[l][l+s-1] = min(dp[l][l+s-1], dp[l][l+s-1-1]+A); } int num=2, nex=nextOccur[l][s]; while(nex<N){ int r=nex+s-1; dp[l][r] = min(dp[l][r], dp[l][l+s-1]+B+C*num+(r-l+1 - num*s)*A); dp[l][r] = min(dp[l][r], A+dp[l+1][r]); dp[l][r] = min(dp[l][r], dp[l][r-1]+A); nex=nextOccur[nex][s]; num++; } } } cout<<dp[0][N-1]<<endl; }

컴파일 시 표준 에러 (stderr) 메시지

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:29:12: warning: unused variable 'out' [-Wunused-variable]
   29 |         ll out=A*N;
      |            ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...