답안 #950248

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950248 2024-03-20T07:18:54 Z GrindMachine Vim (BOI13_vim) C++17
35.3333 / 100
2000 ms 524288 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n; cin >> n;
    string s; cin >> s;
    s = "$" + s;

    ll nxt[n+5][10];
    memset(nxt,0x3f,sizeof nxt);
    array<ll,10> closest;
    closest.fill(inf2);

    rev(i,n,1){
        rep(j,10){
            nxt[i][j] = closest[j];
        }
        closest[s[i]-'a'] = i;
    }

    vector<ll> p(n+5);
    rep1(i,n) p[i] = p[i-1]+(s[i] == 'e');
    ll m = p[n];

    vector<ll> pos;
    pos.pb(0);
    rep1(i,n){
        if(s[i] == 'e'){
            pos.pb(i);
        }
    }

    ll dp[n+5][m+5];
    memset(dp,0x3f,sizeof dp);
    dp[1][0] = 0;

    rep1(i,n){
        rep(j,m){
            if(s[i] == 'e'){
                dp[i][j] = inf2;
                conts;
            }

            rep(ch,10){
                if(ch == 4) conts;
                // if(dp[i][j]) conts;

                ll k = nxt[i][ch];
                if(k > n) conts;

                ll first_new = pos[j+1];
                ll cnt = 0;
                if(first_new <= k){
                    cnt = p[k]-p[first_new-1];
                }

                for(int x = i; x <= min(first_new,k); ++x){
                    amin(dp[x][p[k]],dp[i][j]+2+cnt+k-x);
                }

                bool dbg = false;
                if(i == 4 and j == 2 and ch == 5){
                    // dbg = true;
                }

                if(cnt and first_new+1 <= k){
                    ll x = first_new+1;
                    ll two_cnt = cnt-1;
                    ll one_cnt = k-(x-1)+1-two_cnt;
                    amin(dp[x][p[k]],dp[i][j]+2+2*two_cnt+one_cnt);

                    if(dbg){
                        debug(one_cnt);
                        debug(two_cnt);
                    }

                    // if(x == 10 and p[k] == 3){
                    //     if(dp[i][j]+2+2*two_cnt+one_cnt == 12){
                    //         debug(i);
                    //         debug(j);
                    //         debug(ch);
                    //         debug(dp[i][j]);
                    //     }
                    // }
                }
            }
        }
    }

    // debug(dp[10][3]);

    ll ans = inf2;
    rep1(i,n){
        amin(ans,dp[i][m]);
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

vim.cpp: In function 'void solve(int)':
vim.cpp:46:18: warning: statement has no effect [-Wunused-value]
   46 | #define debug(x) 42
      |                  ^~
vim.cpp:130:25: note: in expansion of macro 'debug'
  130 |                         debug(one_cnt);
      |                         ^~~~~
vim.cpp:46:18: warning: statement has no effect [-Wunused-value]
   46 | #define debug(x) 42
      |                  ^~
vim.cpp:131:25: note: in expansion of macro 'debug'
  131 |                         debug(two_cnt);
      |                         ^~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 1372 KB Output isn't correct
2 Incorrect 6 ms 1368 KB Output isn't correct
3 Incorrect 6 ms 860 KB Output isn't correct
4 Correct 8 ms 1060 KB Output is correct
5 Correct 10 ms 1104 KB Output is correct
6 Correct 9 ms 1368 KB Output is correct
7 Correct 10 ms 1116 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Incorrect 25 ms 1372 KB Output isn't correct
14 Incorrect 7 ms 860 KB Output isn't correct
15 Incorrect 5 ms 860 KB Output isn't correct
16 Incorrect 7 ms 1096 KB Output isn't correct
17 Correct 11 ms 856 KB Output is correct
18 Correct 6 ms 860 KB Output is correct
19 Incorrect 6 ms 860 KB Output isn't correct
20 Correct 7 ms 960 KB Output is correct
21 Correct 10 ms 860 KB Output is correct
22 Correct 10 ms 860 KB Output is correct
23 Correct 10 ms 860 KB Output is correct
24 Correct 8 ms 860 KB Output is correct
25 Correct 5 ms 860 KB Output is correct
26 Correct 5 ms 860 KB Output is correct
27 Correct 7 ms 1116 KB Output is correct
28 Correct 9 ms 1228 KB Output is correct
29 Incorrect 10 ms 1116 KB Output isn't correct
30 Incorrect 11 ms 1020 KB Output isn't correct
31 Correct 8 ms 860 KB Output is correct
32 Incorrect 6 ms 860 KB Output isn't correct
33 Correct 5 ms 860 KB Output is correct
34 Correct 7 ms 960 KB Output is correct
35 Correct 8 ms 1112 KB Output is correct
36 Correct 10 ms 1116 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1429 ms 120408 KB Output isn't correct
2 Correct 913 ms 93520 KB Output is correct
3 Incorrect 497 ms 32940 KB Output isn't correct
4 Incorrect 1349 ms 120404 KB Output isn't correct
5 Execution timed out 2032 ms 85412 KB Time limit exceeded
6 Execution timed out 2045 ms 54360 KB Time limit exceeded
7 Execution timed out 2025 ms 103844 KB Time limit exceeded
8 Incorrect 1653 ms 99412 KB Output isn't correct
9 Correct 921 ms 93292 KB Output is correct
10 Incorrect 1127 ms 87532 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Runtime error 257 ms 524288 KB Execution killed with signal 9
2 Runtime error 241 ms 524288 KB Execution killed with signal 9
3 Runtime error 252 ms 524288 KB Execution killed with signal 9
4 Runtime error 241 ms 524288 KB Execution killed with signal 9
5 Runtime error 255 ms 524288 KB Execution killed with signal 9
6 Runtime error 256 ms 524288 KB Execution killed with signal 9
7 Runtime error 270 ms 524288 KB Execution killed with signal 9
8 Runtime error 246 ms 524288 KB Execution killed with signal 9
9 Runtime error 259 ms 524288 KB Execution killed with signal 9
10 Runtime error 243 ms 524288 KB Execution killed with signal 9
11 Runtime error 245 ms 524288 KB Execution killed with signal 9
12 Runtime error 240 ms 524288 KB Execution killed with signal 9
13 Runtime error 258 ms 524288 KB Execution killed with signal 9
14 Runtime error 257 ms 524288 KB Execution killed with signal 9
15 Runtime error 247 ms 524288 KB Execution killed with signal 9
16 Runtime error 243 ms 524288 KB Execution killed with signal 9
17 Runtime error 247 ms 524288 KB Execution killed with signal 9
18 Runtime error 246 ms 524288 KB Execution killed with signal 9
19 Runtime error 242 ms 524288 KB Execution killed with signal 9
20 Runtime error 242 ms 524288 KB Execution killed with signal 9