oj.uz

Submission #63274

# Submission time Handle Problem Language Result Execution time Memory
63274 2018-08-01T08:22:15 Z 윤교준(#1834) Vim (BOI13_vim) C++11
6.94444 / 100
 1169 ms 79928 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const bool debug = 0;
const int MAXN = 5005;

vector<pii> G[MAXN];
int D[MAXN][MAXN];
int dp[MAXN][MAXN];

vector<int> CV[11];
vector<int> IV;

int B[MAXN];
char A[MAXN];

int N, Ans;

int f(int x, int y) {
	int n = sz(IV);
	if(x+1 == n) return 0;
	int &ret = dp[x][y];
	if(ret < INF) return ret;

	int s = x+1, e = n-1; for(int m1, m2, t1, t2; 10 < e-s;) {
		m1 = (s*2+e) / 3;
		m2 = (s+e*2) / 3;
		t1 = f(m1, x+1) + D[IV[y]][IV[m1]] + D[IV[m1]][IV[x+1]];
		t2 = f(m2, x+1) + D[IV[y]][IV[m2]] + D[IV[m2]][IV[x+1]];

		if(t1 >= t2) s = m1;
		else e = m2;
	}

	for(int t = s; t <= e; t++)
		upmin(ret, f(t, x+1) + D[IV[y]][IV[t]] + D[IV[t]][IV[x+1]]);
	return ret;
}

int main() {
	scanf("%d %s", &N, A+1);

	{
		vector<int> V, VI(1, 0);
		for(int i = 1; i <= N; i++) {
			if('e' == A[i]) {
				Ans += 2;
				continue;
			}
			V.eb(A[i]-'a'+1);
			if('e' == A[i-1]) VI.eb(sz(V)-1);
		}

		N = sz(V);
		for(int i = 1; i <= N; i++)
			B[i] = V[i-1];
		for(int v : VI) IV.eb(v+1);
	}
	if(!Ans) {
		puts("0");
		return 0;
	}

	if(debug) {
		printf("N=%d\n", N);
		for(int i = 1; i <= N; i++)
			printf("%d ", B[i]);
		puts("");
		for(int v : IV) printf("%d ", v);
		puts("");
	}

	for(int i = 1; i <= N; i++) CV[B[i]].eb(i);
	for(int i = 2; i <= N; i++) G[i].eb(i-1, 1);
	{
		int col[11] = {0, };
		for(int i = N; i; i--) {
			for(int j = 1; j <= 10; j++)
				if(col[j]) G[i].eb(col[j], 2);
			col[B[i]] = i;
		}
	}
	
	for(int i = 1; i <= N; i++) {
		priority_queue<pii, vector<pii>, greater<pii>> PQ;
		fill(D[i], D[i]+N+1, INF);
		D[i][i] = 0; PQ.push(pii(0, i));
		
		for(int idx, dst; !PQ.empty();) {
			tie(dst, idx) = PQ.top(); PQ.pop();
			if(D[i][idx] < dst) continue;

			for(auto &e : G[idx]) {
				int nidx = e.first;
				int ndst = dst + e.second;

				if(D[i][nidx] <= ndst) continue;
				D[i][nidx] = ndst;
				PQ.push(pii(ndst, nidx));
			}
		}
	}
	
	for(int i = 0; i < sz(IV); i++)
		fill(dp[i], dp[i]+sz(IV), INF);
	
	Ans += f(0, 0);

	cout << Ans << endl;
	return 0;
}

Compilation message

vim.cpp: In function 'int main()':
vim.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %s", &N, A+1);
  ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
6.94444444444 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 2424 KB Output isn't correct
2 Incorrect 10 ms 2792 KB Output isn't correct
3 Incorrect 7 ms 2792 KB Output isn't correct
4 Incorrect 10 ms 2792 KB Output isn't correct
5 Incorrect 10 ms 2792 KB Output isn't correct
6 Incorrect 11 ms 3104 KB Output isn't correct
7 Incorrect 11 ms 3112 KB Output isn't correct
8 Correct 3 ms 3112 KB Output is correct
9 Correct 3 ms 3112 KB Output is correct
10 Correct 3 ms 3112 KB Output is correct
11 Correct 3 ms 3112 KB Output is correct
12 Correct 3 ms 3112 KB Output is correct
13 Incorrect 8 ms 3112 KB Output isn't correct
14 Incorrect 11 ms 3112 KB Output isn't correct
15 Incorrect 9 ms 3112 KB Output isn't correct
16 Incorrect 9 ms 3112 KB Output isn't correct
17 Incorrect 19 ms 3300 KB Output isn't correct
18 Incorrect 10 ms 3300 KB Output isn't correct
19 Incorrect 7 ms 3300 KB Output isn't correct
20 Incorrect 9 ms 3300 KB Output isn't correct
21 Incorrect 12 ms 3300 KB Output isn't correct
22 Incorrect 11 ms 3300 KB Output isn't correct
23 Incorrect 13 ms 3392 KB Output isn't correct
24 Incorrect 15 ms 3392 KB Output isn't correct
25 Incorrect 14 ms 3392 KB Output isn't correct
26 Incorrect 16 ms 3392 KB Output isn't correct
27 Incorrect 12 ms 3392 KB Output isn't correct
28 Incorrect 12 ms 3392 KB Output isn't correct
29 Incorrect 14 ms 3392 KB Output isn't correct
30 Incorrect 12 ms 3424 KB Output isn't correct
31 Incorrect 13 ms 3424 KB Output isn't correct
32 Incorrect 15 ms 3424 KB Output isn't correct
33 Incorrect 15 ms 3424 KB Output isn't correct
34 Incorrect 13 ms 3424 KB Output isn't correct
35 Incorrect 8 ms 3424 KB Output isn't correct
36 Incorrect 11 ms 3424 KB Output isn't correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 372 ms 36700 KB Output isn't correct
2 Incorrect 759 ms 70428 KB Output isn't correct
3 Incorrect 240 ms 70428 KB Output isn't correct
4 Incorrect 331 ms 70428 KB Output isn't correct
5 Incorrect 824 ms 70428 KB Output isn't correct
6 Incorrect 1169 ms 79928 KB Output isn't correct
7 Incorrect 575 ms 79928 KB Output isn't correct
8 Incorrect 581 ms 79928 KB Output isn't correct
9 Incorrect 808 ms 79928 KB Output isn't correct
10 Incorrect 814 ms 79928 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 12 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 11 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 14 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 8 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 10 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 10 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 13 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 13 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 10 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 14 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 13 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 9 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 10 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 12 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 14 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 10 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 10 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 10 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 13 ms 79928 KB Execution killed with signal 11 (could be triggered by violating memory limits)