Submission #549237

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
549237	2022-04-15T12:31:35 Z	Ronin13	Copy and Paste 3 (JOI22_copypaste3)	C++14	Compilation error	0 ms	0 KB

copypaste3

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;

const int NMAX = 2501;
const int inf = 1e9 + 1;
const ll linf = 1e18 + 1;
ll mod[] ={1000000007, 1000000009, 998244353};
ll pr[] = {29, 31, 37};

ll po[NMAX][3];
ll h[NMAX][3];

void hashing(string s){
    h[0][0] = 0;
    h[0][1] = 0;
    h[0][2] = 0;
    int n = s.size();
    for(int i = 1; i <= n; i++){
        ll x = s[i - 1] - 'a' + 1;
        for(int j = 0; j < 3; j++){
            h[i][j] = h[i - 1][j] * pr[j] + x;
            h[i][j] %= mod[j];
        }
    }
}

int get(int l, int r, int ind){
    ll x = h[r][ind] - h[l - 1][ind] * po[r - l + 1][ind];
    x %= mod[ind];
    x += mod[ind];
    x %= mod[ind];
    return x;
}

ll dp[NMAX][NMAX];
short adj[NMAX][NMAX];

map<pii, int> mp;
vector <pii> vec[NMAX];

int main(){
    po[0][0] = po[0][1] = po[0][2] = 1;
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for(int k = 0; k < 3; k++){
    for(int i = 1; i <=n; i++){
        po[i][k] = po[i - 1][k] * pr[k];
        po[i][k] %= mod[k];
    }
    }
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            dp[i][j] = linf;
        }
    }
    string s; cin >> s;
    ll a, b, c;
    cin >> a >> b >> c;
    hashing(s);
    for(int i = 1; i <= n; i++){
        for(int to : vec[i - 1]) mp[to] = i - 1;
        for(int j = i; j <= n; j++){
            int x = get(i, j, 0);
            int x1 = get(i, j, 1);
            int v = mp[{x, x1}];
            if(v != 0)
            adj[i][j - i + 1] = v - (j - i);
            vec[j].pb({x, x1});
        }
    }
    /*for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout << adj[i][j] << ' ';
        }
        cout << "\n";
    }*/
    vector <int> v[NMAX];
    ll cnt[n + 1];
    for(ll r = 1; r <= n; r++){
        for(int i = 1; i <= n; i++)v[i].clear();
        for(int i = 0; i <= n; i++)cnt[i] = 0;
        for(int i = 1; i <= r; i++){
            int cur = r - i + 1;
            while(cur){
                v[cur].pb(i);
                cur = adj[cur][i];
            }
        }
        ll mn = 0;
        dp[r][r] = a;
        for(int l = r; l >= 1; l--){
            for(int ind = 0; ind < v[l].size(); ind++){
                int to = v[l][ind];
                cnt[to]++;
                ll val = dp[r - to + 1][r] + b;
                val += (c - (ll)to * a) * cnt[to];
                mn = min(mn, val);
            }
            dp[l][r] = mn + (ll)(r - l + 1) * a;
            dp[l][r] = min(dp[l][r], dp[l][r - 1] + a);
        }
    }
    /*for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(dp[i][j] == linf) cout << "-1 ";
            else cout << dp[i][j] << " ";
        }
        cout << "\n";
    }*/
    cout << dp[1][n];
    return 0;
}

Compilation message

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:69:31: error: cannot convert 'std::pair<int, int>' to 'int' in initialization
   69 |         for(int to : vec[i - 1]) mp[to] = i - 1;
      |                               ^
copypaste3.cpp:69:36: error: no match for 'operator[]' (operand types are 'std::map<std::pair<int, int>, int>' and 'int')
   69 |         for(int to : vec[i - 1]) mp[to] = i - 1;
      |                                    ^
In file included from /usr/include/c++/10/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from copypaste3.cpp:1:
/usr/include/c++/10/bits/stl_map.h:492:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](const key_type&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  492 |       operator[](const key_type& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:492:34: note:   no known conversion for argument 1 from 'int' to 'const key_type&' {aka 'const std::pair<int, int>&'}
  492 |       operator[](const key_type& __k)
      |                  ~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_map.h:512:7: note: candidate: 'std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type& std::map<_Key, _Tp, _Compare, _Alloc>::operator[](std::map<_Key, _Tp, _Compare, _Alloc>::key_type&&) [with _Key = std::pair<int, int>; _Tp = int; _Compare = std::less<std::pair<int, int> >; _Alloc = std::allocator<std::pair<const std::pair<int, int>, int> >; std::map<_Key, _Tp, _Compare, _Alloc>::mapped_type = int; std::map<_Key, _Tp, _Compare, _Alloc>::key_type = std::pair<int, int>]'
  512 |       operator[](key_type&& __k)
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_map.h:512:29: note:   no known conversion for argument 1 from 'int' to 'std::map<std::pair<int, int>, int>::key_type&&' {aka 'std::pair<int, int>&&'}
  512 |       operator[](key_type&& __k)
      |                  ~~~~~~~~~~~^~~
copypaste3.cpp:100:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for(int ind = 0; ind < v[l].size(); ind++){
      |                              ~~~~^~~~~~~~~~~~~