답안 #63281

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63281 2018-08-01T08:29:55 Z 윤교준(#1834) Vim (BOI13_vim) C++11
56 / 100
2000 ms 111600 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], E[MAXN][MAXN], F[MAXN][MAXN];
int dp[MAXN][MAXN];

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

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

int N, Ans;

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));
			}
		}
	}

	{
		int n = sz(IV);
		
		for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) {
			E[i][j] = D[IV[i]][IV[j]];
			F[i][j] = D[IV[j]][IV[i]];
		}

		for(int x = n-1; x--;) {
			for(int y = 0; y <= x; y++) {
				int &ret = dp[x][y]; ret = INF;
				for(int t = x+1, tmp; t < n; t++) {
					tmp = dp[t][x+1] + E[y][t] + F[x+1][t];
					if(tmp < ret) ret = tmp;
				}
			}
		}
	}
	Ans += dp[0][0];

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

Compilation message

vim.cpp: In function 'int main()':
vim.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %s", &N, A+1);
  ~~~~~^~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 3704 KB Output is correct
2 Correct 11 ms 4452 KB Output is correct
3 Correct 7 ms 4452 KB Output is correct
4 Correct 16 ms 4452 KB Output is correct
5 Correct 11 ms 4452 KB Output is correct
6 Correct 14 ms 5436 KB Output is correct
7 Correct 14 ms 5436 KB Output is correct
8 Correct 4 ms 5436 KB Output is correct
9 Correct 2 ms 5436 KB Output is correct
10 Correct 1 ms 5436 KB Output is correct
11 Correct 2 ms 5436 KB Output is correct
12 Correct 2 ms 5436 KB Output is correct
13 Correct 12 ms 5436 KB Output is correct
14 Correct 11 ms 5436 KB Output is correct
15 Correct 8 ms 5436 KB Output is correct
16 Correct 10 ms 5436 KB Output is correct
17 Correct 15 ms 5436 KB Output is correct
18 Correct 10 ms 5436 KB Output is correct
19 Correct 9 ms 5436 KB Output is correct
20 Correct 10 ms 5436 KB Output is correct
21 Correct 10 ms 5436 KB Output is correct
22 Correct 11 ms 5436 KB Output is correct
23 Correct 12 ms 5436 KB Output is correct
24 Correct 15 ms 5436 KB Output is correct
25 Correct 14 ms 5436 KB Output is correct
26 Correct 13 ms 5436 KB Output is correct
27 Correct 14 ms 5436 KB Output is correct
28 Correct 14 ms 5468 KB Output is correct
29 Correct 13 ms 5468 KB Output is correct
30 Correct 13 ms 5468 KB Output is correct
31 Correct 13 ms 5468 KB Output is correct
32 Correct 14 ms 5468 KB Output is correct
33 Correct 14 ms 5468 KB Output is correct
34 Correct 12 ms 5468 KB Output is correct
35 Correct 12 ms 5468 KB Output is correct
36 Correct 14 ms 5468 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1415 ms 62112 KB Output is correct
2 Execution timed out 2057 ms 111600 KB Time limit exceeded
3 Correct 381 ms 111600 KB Output is correct
4 Correct 1433 ms 111600 KB Output is correct
5 Execution timed out 2060 ms 111600 KB Time limit exceeded
6 Correct 1947 ms 111600 KB Output is correct
7 Correct 1883 ms 111600 KB Output is correct
8 Correct 1815 ms 111600 KB Output is correct
9 Execution timed out 2063 ms 111600 KB Time limit exceeded
10 Execution timed out 2071 ms 111600 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 13 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 13 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 11 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 13 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 14 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 13 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 11 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 12 ms 111600 KB Execution killed with signal 11 (could be triggered by violating memory limits)