oj.uz

답안 #724685

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
724685 2023-04-15T17:47:16 Z MohammadAghil Copy and Paste 3 (JOI22_copypaste3) C++17
0 / 100
 2 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define all(x) begin(x), end(x)
#define sz(x) (int)size(x)
#define pb push_back
#define ff first
#define ss second
typedef long long ll;
typedef pair<int, int> pp;

void dbg(){
     cerr << endl;
}
template<typename H, typename... T> void dbg(H h, T... t){
     cerr << h << ", ";
     dbg(t...);
}

void IOS(){
     cin.tie(0) -> sync_with_stdio(0);
     #ifndef ONLINE_JUDGE
          freopen("inp.txt", "r", stdin);
          freopen("out.txt", "w", stdout);
          #define er(...) cerr << __LINE__ << " <" << #__VA_ARGS__ << ">: ", dbg(__VA_ARGS__)
     #else
          #define er(...) 0
     #endif
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll mod = 1e9 + 7, mod2 = 1e9 + 9, maxn = 25e2 + 5, lg = 21, inf = ll(1e18) + 5, p = 9973;

ll dp[maxn][maxn];
ll pw[2][maxn], hsh[2][maxn];

void buildHsh(string s){
     hsh[0][0] = hsh[1][0] = s[0];
     rep(i,1,sz(s)){
          hsh[0][i] = (hsh[0][i-1]*p%mod + s[i])%mod;
          hsh[1][i] = (hsh[1][i-1]*p%mod2 + s[i])%mod2;
     }
     pw[0][0] = pw[1][0] = 1;
     rep(i,1,sz(s)+1) {
          pw[0][i] = pw[0][i-1]*p%mod;
          pw[1][i] = pw[1][i-1]*p%mod2;
     }
}

pp get(int l, int r){
     return {
          (hsh[0][r] - (l? hsh[0][l-1]*pw[0][r-l+1]%mod: 0) + mod)%mod,
          (hsh[1][r] - (l? hsh[1][l-1]*pw[1][r-l+1]%mod2: 0) + mod2)%mod2
     };
}

int main(){ IOS();
     int n; cin >> n;
     string s; cin >> s;
     ll A, C, P; cin >> A >> C >> P;
     rep(i,0,n){
          rep(j,i,n) dp[i][j] = inf;
     }
     buildHsh(s);
     rep(l,1,n+1){
          map<pp, int> mp;
          vector<int> prv(n, -1);
          rep(i,0,n-l+1){
               int j = i + l - 1;
               if(i < j) dp[i][j] = min({dp[i][j], dp[i+1][j] + A, dp[i][j-1] + A});
               else dp[i][j] = A;
               if(i >= l) mp[get(i-l, i-1)] = i-l;
               pp cr = get(i, j);
               if(mp.count(cr)) prv[i] = mp[cr];
               int x = prv[i];
               int cnt = 2;
               while(x + 1){
                    dp[x][j] = min(dp[x][j], P*cnt + dp[i][j] + C + (j - x + 1 - l*cnt)*A);
                    x = prv[x];
                    cnt++;
               }
          }    
     }
     cout << dp[0][n-1] << '\n';
     return 0;
}

Compilation message

copypaste3.cpp: In function 'void IOS()':
copypaste3.cpp:24:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |           freopen("inp.txt", "r", stdin);
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
copypaste3.cpp:25:18: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |           freopen("out.txt", "w", stdout);
      |           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -