Submission #1267917

#TimeUsernameProblemLanguageResultExecution timeMemory
1267917_rain_Vim (BOI13_vim)C++20
0 / 100
14 ms2120 KiB
#include<bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i,a,b) for(int i = (a) , _b = (b); i <= _b; ++i) #define BIT(mask , x) (((mask) >> (x)) & (1)) #define MASK(x) ((LL)(1) << (x)) #define sz(x) (int)(x).size() #define TIME_USED cerr << "\n Time lapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << "s \n"; template<class T1 , class T2> bool maximize(T1 &a , T2 b){ if (a < b) return a = b , true; else return false; } template<class T1 , class T2> bool minimize(T1 &a , T2 b){ if (a > b) return a = b , true; else return false; } template<class T1 , class T2> T2 Find(const vector<T1>&data , T2 y){ return upper_bound(data.begin() , data.end() , y) - data.begin(); } template<class T> void compress(vector<T>&data){ sort(data.begin() , data.end()); data.resize(unique(data.begin() , data.end()) - data.begin()); } const int N = (int) 7e4; const int inf = (int) 1e9; const int MAXK = (int) 11; const int const_id = 4; vector<int> occur[MAXK + 2]; int a[N + 2]; string s; int n; int Find_nxt(int c , int x){ int tt = lower_bound(occur[c].begin() , occur[c].end() , x) - occur[c].begin(); --tt; if (tt == -1) return tt; return occur[c][tt]; } //... ARRAY FOR PROCESSING int dp[N + 2][2] = {}; int rig[N + 2] = {}; int pre[N + 2] = {}; int Get_prefix(int l , int r){ return pre[r] - pre[l - 1]; } int main(){ ios::sync_with_stdio(false); cin.tie(0) ; cout.tie(0) ; #define name "main" if (fopen(name".inp","r")){ freopen(name".inp","r",stdin); freopen(name".out","w",stdout); } cin >> n >> s; s = '#' + s; for(int i = 1; i <= n; ++i) a[i] = (int)s[i] - 'a'; for(int i = 1; i <= n; ++i) occur[a[i]].push_back(i); //... PRE BUILD rig[n + 1] = n + 1; for(int i = n; i >= 1; --i){ if (a[i] == const_id) rig[i] = i; else rig[i] = rig[i + 1]; } for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + (a[i] == const_id); int start = 1 , ans = 0; memset(dp , 0x3f , sizeof dp); dp[start][1] = dp[start][0] = ans; for(int i = start; i <= n; ++i){ if (a[i] == const_id) continue; for(int j = 0; j <= MAXK; ++j){ if (j == const_id) continue; int t = Find_nxt(j , i); if (t == -1) continue; int last_ptr = min(rig[t] , i); minimize(dp[i][0] , dp[t][1] + 2 + Get_prefix(t , i) + i - last_ptr); } minimize(dp[i][1] , dp[i][0]); } ans = inf; for(int i = 1; i <= n; ++i) if (pre[i] == pre[n]) minimize(ans , dp[i][1]); cout << ans; return 0; }

Compilation message (stderr)

vim.cpp: In function 'int main()':
vim.cpp:60:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
vim.cpp:61:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...