oj.uz

Submission #724678

# Submission time Handle Problem Language Result Execution time Memory
724678 2023-04-15T17:37:46 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 = 998244353, maxn = 25e2 + 5, lg = 21, inf = ll(1e18) + 5, p = 9973;

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

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

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

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<int, 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;
               int 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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -