oj.uz

Submission #318165

# Submission time Handle Problem Language Result Execution time Memory
318165 2020-10-31T14:36:24 Z greengrass19000 Bajka (COCI20_bajka) C++14
70 / 70
 27 ms 748 KB 
/**Bogosort**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxn 305
#define maxm 1000006
#define maxc 1000000007
#define pii pair <int,int>
#define ii pair <int,int>
#define Task ""
//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n, m, dp[maxn][maxn];
char fear[maxn], like[maxn];
int main() {
    //srand(time(NULL));
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie();
    if(fopen(".inp", "r")) freopen(".inp", "r", stdin);
	cin >> m >> n;
	fo(i, 1, m) cin >> fear[i];
	fo(j, 1, n) cin >> like[j];
//	dp[i][j] i = like, j = fear jump by j
	fo(j, 1, m) if(fear[j] == like[1]) dp[1][j] = 1; 
	fo(i, 1, n) {
		fo(j, 1, m) if(dp[i][j]) {
			fo(k, 1, m) if(fear[k] == fear[j]) {
				if(fear[k-1] == like[i+1]) {
					if(!dp[i+1][k-1] || dp[i+1][k-1] > dp[i][j] + abs(k - j) + 1) 
						dp[i+1][k-1] = dp[i][j] + abs(k - j) + 1;
				}
				if(fear[k+1] == like[i+1]) {
					if(!dp[i+1][k+1] || dp[i+1][k+1] > dp[i][j] + abs(k - j) + 1) 
						dp[i+1][k+1] = dp[i][j] + abs(k - j) + 1;
				}
			}
		}
	}
	int ans = 2e9;
	fo(j, 1, m) if(dp[n][j] && dp[n][j] < ans) ans = dp[n][j];
	if(ans == 2e9) return cout << -1, 0;
	cout << ans - 1;
	return 0;
}

Compilation message

bajka.cpp: In function 'int main()':
bajka.cpp:29:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   29 |     if(fopen(".inp", "r")) freopen(".inp", "r", stdin);
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 7 ms 748 KB Output is correct
8 Correct 27 ms 748 KB Output is correct
9 Correct 20 ms 748 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 5 ms 748 KB Output is correct