oj.uz

Submission #493143

# Submission time Handle Problem Language Result Execution time Memory
493143 2021-12-10T06:45:26 Z Koying Semiexpress (JOI17_semiexpress) C++14
0 / 100
 122 ms 348 KB 
#pragma region
#pragma optimize("O3")
#include <bits/stdc++.h>
#define Weakoying ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define pqueue priority_queue
#define pb push_back
#define F first
#define S second
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define cmax(a, b) a = (a > b ? a : b)
#define cmin(a, b) a = (a < b ? a : b)
#define put(x) cout << x << endl;
#define putarr(x) for(int i = 0; i < sizeof(x); i++) cout << x[i] << (" \n")[i == sizeof(x) - 1]; 
#define stop system("pause");
#define MEM(x, n) memset(x, n, sizeof(x));
#define lowbit(x) x &(-x)
#if !LOCAL
#define endl "\n"
#endif
const int INF = 0x3f3f3f3f;
const int P = 1e9+7;

using namespace std;
#pragma endregion
/******************************************************************************/
#define MAXN 100005
#define MAXM 3005
int n, m, k, t;
int A, B, C;
int x[MAXM];
pii dis[MAXM];

void find_dist()
{
	MEM(dis, 63);
	dis[1] = {0, 0};
	for(int i = 1; i < m; i++)
	{
		dis[x[i]].F = B * (x[i] - 1);
		dis[x[i]].S = 0;
	}
	for(int i = 2; i <= n; i++)
	{
		cmin(dis[i].F, A * (i - 1));
		int F = upper_bound(x, x + m, i) - x;
		if(F != m)
		{
			cmin(dis[i].F, dis[x[F]].F + A * (abs(x[F] - i)));
			cmin(dis[i].S, abs(x[F] - i));
			
		}
		F--;
		cmin(dis[i].F, dis[x[F]].F + A * (abs(x[F] - i)));
		cmin(dis[i].S, abs(x[F] - i));
	}
	// for(int i = 1; i <= n; i++)
		// cout << dis[i].F << " ";
	// cout << endl;
	// for(int i = 1; i <= n; i++)
		// cout << dis[i].S << " ";
	// cout << endl;
}

void sol()
{
	cin >> n >> m >> k;
	cin >> A >> B >> C;
	cin >> t;
	set<int> s;
	for(int i = 0; i < m; i++)
	{
		cin >> x[i];
	}
	find_dist();
	// int ans = 0;
	// for(int i = 2; i <= n; i++)
	// {
		// if(dis[i].F <= t) 
		// ans++;
	// }
	// // cout << ans << endl;
	// sort(dis + 1, dis + n + 1, greater<pii>());
	// for(int i = 1; dis[i].F > t && k > m && i <= n; i++)
	// {
		// // cout << dis[i].F << endl;
		// if(dis[i].F - dis[i].S * (A - C) <= t)
		// {
			// ans++;
			// k--;
		// }
	// }
	// cout << ans << endl;
	if(k - m == 2)
	{
		int ans = 0;
		for(int i = 2; i < n; i++)
		{
			int ouo = 0;
			if(binary_search(x, x + m, i)) continue;
			for(int j = i + 1; j <= n; j++)
			{
				if(binary_search(x, x + m, j)) continue;	
				int cnt = 0;			
				for(int k = 2; k <= n; k++)
				{
					int tmp = INF;
					int F = upper_bound(x, x + m, k) - x;
					if(F != m)
						cmin(tmp, B * (x[F] - k) + dis[x[F]].F);
					cmin(tmp, B * (k - x[F - 1]) + dis[x[F]].F);
					cmin(tmp, C * (abs(k - i) - 1) + dis[i].F);
					cmin(tmp, C * (abs(k - j) - 1) + dis[j].F);
					if(tmp <= t)
						cnt++;
				}
				cmax(ans, cnt);
			}
			// cout << i << " " << ouo << endl;
		}
		cout << ans << endl;
	}
}

signed main()
{
    Weakoying;
    int t = 1;
    //while (cin >> t)
    {
    	while (t--)
        {
            sol();
        }
    }
        
    return 0;
}

Compilation message

semiexpress.cpp:1: warning: ignoring '#pragma region ' [-Wunknown-pragmas]
    1 | #pragma region
      | 
semiexpress.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize("O3")
      | 
semiexpress.cpp:29: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   29 | #pragma endregion
      | 
semiexpress.cpp: In function 'void find_dist()':
semiexpress.cpp:20:41: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment [-Wclass-memaccess]
   20 | #define MEM(x, n) memset(x, n, sizeof(x));
      |                                         ^
semiexpress.cpp:40:2: note: in expansion of macro 'MEM'
   40 |  MEM(dis, 63);
      |  ^~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from semiexpress.cpp:3:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~
semiexpress.cpp: In function 'void sol()':
semiexpress.cpp:103:8: warning: unused variable 'ouo' [-Wunused-variable]
  103 |    int ouo = 0;
      |        ^~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 332 KB Output is correct
2 Incorrect 122 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 332 KB Output is correct
2 Incorrect 122 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 332 KB Output is correct
2 Incorrect 122 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -