oj.uz

Submission #260070

# Submission time Handle Problem Language Result Execution time Memory
260070 2020-08-09T08:28:32 Z arnold518 Vim (BOI13_vim) C++14
55 / 100
 1090 ms 197880 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 5000;

int N;
char A[MAXN+10];
ll dp[MAXN+10][MAXN+10];
vector<int> V[10];

vector<int>::iterator low[MAXN+10][10], upp[MAXN+10][10];

ll solve(int now, int pos)
{
	ll &ret=dp[now][pos];
	if(ret!=-1) return ret;
	ret=1e18;

	for(int i=0; i<10; i++)
	{
		if(i==4) continue;
		auto it=upp[now][i];
		if(it==V[i].end()) continue;
		ret=min(ret, solve(*it, pos)+2);
	}
	if(now>pos)
	{
		ll p=now-pos+low[now][4]-low[pos][4];
		auto jt=upp[now][4];
		if(jt==V[4].end()) ret=min(ret, p);
		else
		{
			for(int i=0; i<10; i++)
			{
				if(i==4) continue;
				auto it=upp[pos+1][i];
				if(it==V[i].end()) continue;
				ret=min(ret, solve(*it, *jt)+p+2);
			}
		}
	}
	//printf("%d %d : %d\n", now, pos, ret);
	return ret;
}

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

	for(int i=1; i<=N; i++) V[A[i]-'a'].push_back(i);
	for(int j=0; j<10; j++) for(int i=1; i<=N; i++) low[i][j]=lower_bound(V[j].begin(), V[j].end(), i);
	for(int j=0; j<10; j++) for(int i=1; i<=N; i++) upp[i][j]=upper_bound(V[j].begin(), V[j].end(), i);

	if(V[4].empty()) return !printf("0\n");
	memset(dp, -1, sizeof(dp));
	printf("%d\n", solve(1, V[4].front()));
}

Compilation message

vim.cpp: In function 'int main()':
vim.cpp:52:17: warning: too many arguments for format [-Wformat-extra-args]
  scanf("%*d", &N);
                 ^
vim.cpp:62:39: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
  printf("%d\n", solve(1, V[4].front()));
                 ~~~~~~~~~~~~~~~~~~~~~~^
vim.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%*d", &N);
  ~~~~~^~~~~~~~~~~
vim.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", A+1);
  ~~~~~^~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 196856 KB Output is correct
2 Correct 104 ms 197064 KB Output is correct
3 Correct 102 ms 196856 KB Output is correct
4 Correct 105 ms 196856 KB Output is correct
5 Correct 105 ms 196856 KB Output is correct
6 Correct 110 ms 196984 KB Output is correct
7 Correct 108 ms 196940 KB Output is correct
8 Correct 102 ms 196856 KB Output is correct
9 Correct 99 ms 196856 KB Output is correct
10 Correct 108 ms 196808 KB Output is correct
11 Correct 99 ms 196856 KB Output is correct
12 Correct 99 ms 196840 KB Output is correct
13 Correct 104 ms 196860 KB Output is correct
14 Correct 112 ms 196856 KB Output is correct
15 Correct 104 ms 196856 KB Output is correct
16 Correct 104 ms 196856 KB Output is correct
17 Correct 107 ms 196984 KB Output is correct
18 Correct 104 ms 196900 KB Output is correct
19 Correct 104 ms 196856 KB Output is correct
20 Correct 104 ms 196856 KB Output is correct
21 Correct 104 ms 196856 KB Output is correct
22 Correct 104 ms 196856 KB Output is correct
23 Correct 105 ms 196856 KB Output is correct
24 Correct 104 ms 196856 KB Output is correct
25 Correct 108 ms 196988 KB Output is correct
26 Correct 106 ms 196856 KB Output is correct
27 Correct 107 ms 196848 KB Output is correct
28 Correct 107 ms 196856 KB Output is correct
29 Correct 109 ms 196892 KB Output is correct
30 Correct 104 ms 196912 KB Output is correct
31 Correct 104 ms 196852 KB Output is correct
32 Correct 105 ms 196856 KB Output is correct
33 Correct 104 ms 196856 KB Output is correct
34 Correct 105 ms 196856 KB Output is correct
35 Correct 104 ms 196984 KB Output is correct
36 Correct 107 ms 196860 KB Output is correct

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 583 ms 197752 KB Output isn't correct
2 Correct 1090 ms 197712 KB Output is correct
3 Incorrect 287 ms 197240 KB Output isn't correct
4 Incorrect 578 ms 197624 KB Output isn't correct
5 Correct 1066 ms 197752 KB Output is correct
6 Correct 968 ms 197880 KB Output is correct
7 Incorrect 686 ms 197624 KB Output isn't correct
8 Incorrect 701 ms 197752 KB Output isn't correct
9 Correct 1076 ms 197752 KB Output is correct
10 Correct 1031 ms 197752 KB Output is correct

Subtask #3
0 / 40.0

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