oj.uz

Submission #355458

# Submission time Handle Problem Language Result Execution time Memory
355458 2021-01-22T13:56:33 Z amunduzbaev Ancient Books (IOI17_books) C++14
0 / 100
 749 ms 1048580 KB 
#include "books.h"
 
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
 
#define ll long long
#define sz(x) (int)x.size()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
 
const ll inf = 1e9+7;
const int N = 1e3+5;
const int mod = 1e9+7;
 
int n, dp[N][N], used[N], last, L[N], R[N], in[N];
int endL, endR;

pii ext(int l, int r){
	int new_l = min(L[in[l]], L[in[r]]), new_r = max(R[in[r]], R[in[l]]);
	while(1){
		if(new_l < l) new_l = min(L[in[--l]], new_l), new_r = max(R[in[l]], new_r);
		else if(new_r > r) new_l = min(L[in[++r]], new_l), new_r = max(R[in[r]], new_r);
		else break;
	}return {new_l, new_r};
}

ll fun(int l, int r){
	if(l < endL || r > endR || l < 0 || r > n) return inf;
	//cout<<l<<" "<<r<<"\n";
	pii tt = ext(l, r);
	l = tt.ff, r = tt.ss;
	if(l == endL && r == endR) return 0;
	int &res = dp[l][r];
	if(res != -1) return res;
	res = min(fun(l-1, r), fun(l, r+1)) + 2;
	return res; 
}

ll minimum_walk(vector<int> p, int s) {
	memset(dp, -1, sizeof dp);
	n = sz(p);
	ll res = 0;
	endL = inf, endR = inf;
	for(int i=0;i<n;i++){
		if(!used[i]){
			int u = i;
			L[last] = u, R[last] = u;
			do{
				used[u] = 1;
				in[u] = last;
				L[last] = min(L[last], u);
				R[last] = max(R[last], u);
				res += abs(p[u] - u);
				u = p[u];
			}while(u != i);
			if(L[last] != R[last]){
				endL = min(L[last], endL);
				endR = max(R[last], endR);
			}
			last++;
		}
	}
	
	return fun(s, s) + res;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4332 KB 3rd lines differ - on the 1st token, expected: '6', found: '1000000011'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4332 KB 3rd lines differ - on the 1st token, expected: '6', found: '1000000011'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4332 KB 3rd lines differ - on the 1st token, expected: '6', found: '1000000011'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 749 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4332 KB 3rd lines differ - on the 1st token, expected: '6', found: '1000000011'
2 Halted 0 ms 0 KB -