Submission #538738

#	Time	Username	Problem	Language	Result	Execution time	Memory
538738		Lobo	Vim (BOI13_vim)	C++17	55 / 100	779 ms	296760 KiB

vim

#include <bits/stdc++.h>
 
using namespace std;
 
const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef long long ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
 
#define maxn 5050
 
ii n, a[maxn], dp[maxn][maxn], mark[maxn][maxn], px[maxn][20], pse[maxn];
 
ii sol(ii i, ii j) {
    if(j == n+1) return 0;
    if(i > n) return INFii;
    if(mark[i][j]) return dp[i][j];
 
    mark[i][j] = 1;
 
    if(a[j] != 'e'-'a') return dp[i][j] = sol(i,j+1);
 
    ii ans = INFii;
 
    for(ii c = 0; c <= 'j'-'a'; c++) {
        if(c == 'e'-'a') continue;
        if(px[i+1][c] != 0) ans = min(ans, sol(px[i+1][c],j)+2); //i+1 para nao contar com ele mesmo
    }
 
    if(j <= i) {
        ans = min(ans, sol(j+1,i+1) + (i-j) + (pse[i]-pse[j-1]));
    }
 
    return dp[i][j] = ans;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
 
    string s;
    cin >> n >> s;
 
    for(ii i = 1; i <= n; i++) {
        pse[i] = pse[i-1];
        if(s[i-1] == 'e') {
            pse[i]++;
        }
 
        a[i] = s[i-1]-'a';
    }
 
    for(ii i = n; i >= 1; i--) {
        for(ii c = 0; c <= 'j'-'a'; c++) {
            px[i][c] = px[i+1][c];
        }
        px[i][a[i]] = i;
    }
 
    for(ii i = 1; i <= n; i++) {
        for(ii c = 0; c <= 'j'-'a'; c++) {
            //cout << i << " " << (char) (c+'a') << " == " << px[i][c] << endl;
        }
    }
 
    cout << sol(1,1) << endl;
}
 

• Subtask 1: 50 / 50
• Subtask 2: 5 / 10
• Subtask 3: 0 / 40